<p>The paper <a href="http://onak.pl/download/publications/Nguyen_Onak-constant_time_approximation.pdf">Constant-Time Approximation Algorithms via Local Improvements</a> by Nguyen and Onak gives a lot of examples of random constant time approximation schemes: Maximum Matching (the running time depends only on the maximum degree of the graph), Set cover, etc. The authors present a method to design such algorithms.</p>

CC BY-SA 3.0
2015-10-12T11:52:43.083Z
2015-10-12T11:52:43.083Z
Lamine
<p>There are many examples of games studied in combinatorial game theory where the state of a game can be described by a constant number of integer values. For some of these, a winning strategy for the game can be computed in constant time. But they also raise questions about what exactly your model of computation is.</p>

<p>One of the simplest and most basic combinatorial games is nim: one has a constant number of piles of beans, and in a single move you can remove any number of beans from one pile, either winning or losing (depending on your choice of rules) if you take the last bean. The optimal strategy can be computed in constant time if you allow bitwise Boolean xor operations (i.e. the ^ operator in programming languages like C/C++/Java/etc.) Is this a constant time algorithm in your model?</p>

<p>Here's one where it is known that there exists a constant time exact deterministic algorithm (in a possibly-unrealistic extended model of computation that allows you to test primality of a number in constant time) but it's not known what that algorithm is: given a starting move in the game of <a href="https://en.wikipedia.org/wiki/Sylver_coinage">Sylver coinage</a>, determine whether it is a winning or losing move. A flowchart for this problem is given in Berlecamp, Conway, and Guy, <em>Winning Ways</em>, but it depends on a finite set of counterexamples to a general characterization of the winning moves, and it's not known what that set is (or even whether it is empty).</p>

<p>Another interesting example from combinatorial game theory is <a href="https://en.wikipedia.org/wiki/Wythoff%27s_game">Wythoff's game</a>. Each game position can be described by a pair of integers (i.e., constant space, in your model of computation), moves in the game involve reducing one of these two integers to a smaller value, and the winning strategy involves moving to a position where the ratio between these two integers is as close to the golden ratio as possible. But in many game positions there is a choice: you can reduce the larger of the two integers either to the point where it is (nearly) the smaller integer times the golden ratio, or the smaller integer divided by the golden ratio. Only one of these two choices will be a winning move. So the optimal strategy can be defined in terms of a constant number of arithmetic operations, but these operations involve an irrational number, the golden ratio. Is that a constant time algorithm in your model? Maybe it's an example of non-uniform constant time, where the algorithm is constant time if it is given access to a constant amount of extra "hint" information that depends on $n$ (an approximation to the golden ratio accurate to $\log n$ bits) but not constant time using only arithmetic operations (no square roots) and fixed integer constants values?</p>

CC BY-SA 3.0
2015-10-14T02:03:16.527Z
Thank you, these are all interesting examples. They also nicely shed light to the fact that the concept of "constant time" is less clear than I originally thought...
Andras Farago
CC BY-SA 3.0
2015-10-13T22:50:31.787Z
2015-10-13T22:50:31.787Z
David Eppstein
<p>Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can be done, since the answer can only depend on a constant length initial segment of the input, as farther parts of the input cannot even be reached in constant time.</p>

<p>On the other hand, if we adopt the somewhat more powerful (and more realistic) unit-cost RAM model, in which elementary operations on $O(\log n)$-bit numbers are counted as single steps, then we may be able to solve nontrivial tasks, even in constant time. Here is an example:</p>

<blockquote>
  <p><strong>Instance:</strong> Integers $n, k, l, d$, each given in binary format by $O(\log n)$ bits.</p>
  
  <p><strong>Question:</strong> Does there exist an $n$-vertex graph, such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$? </p>
</blockquote>

<p>Note that from the definition it is not even obvious that the problem is in <strong>NP</strong>. The reason is that the natural witness (the graph) may need $\Omega(n^2)$-bit long description, while the input is given by only $O(\log n)$ bits. On the other hand, the following theorem (see <em> Extremal Graph Theory </em> by B. Bollobas) comes to the rescue.</p>

<blockquote>
  <p><b>Theorem: </b> Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree  $d$, if and only if one of the following conditions is satisfied: <UL>
  <LI>  $0\leq k\leq l \leq d &lt;\lfloor n/2 \rfloor$, 
  <LI> $1\leq 2d+2-n\leq k\leq l = d&lt; n-1$
  <LI> $k=l=d=n-1.$
  </UL></p>
</blockquote>

<p>Since these conditions can be checked in constant time (in the unit-cost RAM model), the Theorem leads to a constant time algorithm in this model. </p>

<p><strong>Question:</strong> What are some other nontrivial examples of constant time algorithms?</p>

CC BY-SA 3.0
2015-10-11T06:30:58.707Z
Does verifying a probabilistically checkable proof count?
David Eppstein
CC BY-SA 3.0
2015-10-11T09:35:31.380Z
Don't think your example is $O(1)$ time. Your input has length $m=O(\log n)$, in which case the typical word RAM would only allow $O(\log m)$-bit operations in one step. (The alternative is to allow wordsize proportional to the input length, but in that case one can name many "constant-time" algorithms...) You could try to add on a string of length $\geq n$ after those numbers, but then I don't see how checking that format would run in $O(1)$ time: seems you have to check (via binary search, say) that the total string length is indeed $\Omega(\log n)$, which requires $\log n$ time.
Ryan Williams
CC BY-SA 3.0
2015-10-11T09:37:42.430Z
I think David Eppstein's suggestion points to a more interesting direction: considering **randomized** O(1)-time algorithms. At least in that case, you can hope that every input bit is accessed in at least one possible run of the algorithm.
Ryan Williams
CC BY-SA 3.0
2015-10-11T11:38:10.983Z
A simple example of randomised O(1)-time algorithms is approximate median (approximate in the sense that it will split the input roughly 50-50). Simply pick 1000000 elements from the input uniformly at random, calculate their median, and output it.
Jukka Suomela
CC BY-SA 3.0
2015-10-11T14:06:43.887Z
While in the original question I only had deterministic algorithms in mind, the comments convinced me that it is indeed more interesting to allow randomized algorithms, too. Regarding the example in the question, my understanding was that checking the conditions can be done in constant time, if elementary operations on input _numbers_ (or on numbers of the same bit-length) count as single steps. That is, I indeed considered a word size proportional to the bit-length of input numbers.
Andras Farago
CC BY-SA 3.0
2015-10-11T15:06:11.833Z
This is CHEATING: for any *fixed* $k$ decide if the input $x$ is equal to the $k$-th bit of the Chaitin's constant; or for any *fixed* $p$ decide if the input $x$ is such that $(x \mod 2=0) \land HALT(p)$ ... tons of nontrivial problems that could be decided in $O(1)$  :-) :-)
Marzio De Biasi
CC BY-SA 3.0
2015-10-11T18:25:30.527Z
So Jukka's example is constant (probabilistically) in terms of how many samples you have, but non-constant in terms of the size of the universe. So a lot of the times an algorithm can have constant runtime with respect to one variable and non-constant runtime with respect to another variable. But it's probably considered a "non-trivial" constant time solution if it has constant runtime with respect to some variable that would seem to matter in the runtime of the algorithm (in that example it would seem that the amount of samples should matter), I think.
Phylliida
CC BY-SA 3.0
2015-10-11T18:49:42.633Z
Algebraic circuits of constant depth can be an alternative formalization what you posted originally.
Kaveh
CC BY-SA 3.0
2015-10-13T09:03:26.037Z
I like you question but the drawback of your example is that it relies on a mathematical theorem. Pushing this to the limit you could say: **Instance** Positive integers $x, y, z$. **Question** Is there an integer $n > 2$ such that $x^n + y^n = z^n$ (answer is True or False). Well, there is indeed a constant time algorithm because the answer is always False, but this is clearly not the kind of examples you wish.
J.-E. Pin
<cc.complexity-theory><ds.algorithms><time-complexity>
Nontrivial problems solvable in constant time?
Andras Farago
# Nontrivial problems solvable in constant time?

(Asked by: username_0 on 2015-10-10)

Constant time is the absolute low end of time complexity. One may wonder: is there anything nontrivial that can be computed in constant time? If we stick to the Turing machine model, then not much can be done, since the answer can only depend on a constant length initial segment of the input, as farther parts of the input cannot even be reached in constant time.

On the other hand, if we adopt the somewhat more powerful (and more realistic) unit-cost RAM model, in which elementary operations on $O(\log n)$-bit numbers are counted as single steps, then we may be able to solve nontrivial tasks, even in constant time. Here is an example:

> **Instance:** Integers $n, k, l, d$, each given in binary format by $O(\log n)$ bits.
>
> **Question:** Does there exist an $n$-vertex graph, such that its vertex connectivity is $k$, its edge connectivity is $l$, and its minimum degree is $d$?

Note that from the definition it is not even obvious that the problem is in **NP**. The reason is that the natural witness (the graph) may need $\Omega(n^2)$-bit long description, while the input is given by only $O(\log n)$ bits. On the other hand, the following theorem (see  *Extremal Graph Theory*  by B. Bollobas) comes to the rescue.

> **Theorem:**  Let $n, k, l, d$ be integers. There exists an $n$-vertex graph with vertex connectivity $k$, edge connectivity $l$, and minimum degree $d$, if and only if one of the following conditions is satisfied:
>
> * $0\leq k\leq l \leq d <\lfloor n/2 \rfloor$,* $1\leq 2d+2-n\leq k\leq l = d< n-1$* $k=l=d=n-1.$

Since these conditions can be checked in constant time (in the unit-cost RAM model), the Theorem leads to a constant time algorithm in this model.

**Question:** What are some other nontrivial examples of constant time algorithms?

**Tags:** cc.complexity-theory, ds.algorithms, time-complexity

> **Comments:**
> **username_1**: Does verifying a probabilistically checkable proof count?  
> **username_2**: Don't think your example is $O(1)$ time. Your input has length $m=O(\log n)$, in which case the typical word RAM would only allow $O(\log m)$-bit operations in one step. (The alternative is to allow wordsize proportional to the input length, but in that case one can name many "constant-time" algorithms...) You could try to add on a string of length $\geq n$ after those numbers, but then I don't see how checking that format would run in $O(1)$ time: seems you have to check (via binary search, say) that the total string length is indeed $\Omega(\log n)$, which requires $\log n$ time.  
> **username_2**: I think username_1's suggestion points to a more interesting direction: considering **randomized** O(1)-time algorithms. At least in that case, you can hope that every input bit is accessed in at least one possible run of the algorithm.  
> **username_3**: A simple example of randomised O(1)-time algorithms is approximate median (approximate in the sense that it will split the input roughly 50-50). Simply pick 1000000 elements from the input uniformly at random, calculate their median, and output it.  
> **username_0**: While in the original question I only had deterministic algorithms in mind, the comments convinced me that it is indeed more interesting to allow randomized algorithms, too. Regarding the example in the question, my understanding was that checking the conditions can be done in constant time, if elementary operations on input _numbers_ (or on numbers of the same bit-length) count as single steps. That is, I indeed considered a word size proportional to the bit-length of input numbers.  
> **username_4**: This is CHEATING: for any *fixed* $k$ decide if the input $x$ is equal to the $k$-th bit of the Chaitin's constant; or for any *fixed* $p$ decide if the input $x$ is such that $(x \mod 2=0) \land HALT(p)$ ... tons of nontrivial problems that could be decided in $O(1)$  :-) :-)  
> **username_5**: So Jukka's example is constant (probabilistically) in terms of how many samples you have, but non-constant in terms of the size of the universe. So a lot of the times an algorithm can have constant runtime with respect to one variable and non-constant runtime with respect to another variable. But it's probably considered a "non-trivial" constant time solution if it has constant runtime with respect to some variable that would seem to matter in the runtime of the algorithm (in that example it would seem that the amount of samples should matter), I think.  
> **username_6**: Algebraic circuits of constant depth can be an alternative formalization what you posted originally.  
> **username_7**: I like you question but the drawback of your example is that it relies on a mathematical theorem. Pushing this to the limit you could say: **Instance** Positive integers $x, y, z$. **Question** Is there an integer $n > 2$ such that $x^n + y^n = z^n$ (answer is True or False). Well, there is indeed a constant time algorithm because the answer is always False, but this is clearly not the kind of examples you wish.  

---

## 2 answers

### Answer by username_8 on 2015-10-12. Score: 7

The paper [Constant-Time Approximation Algorithms via Local Improvements](http://onak.pl/download/publications/Nguyen_Onak-constant_time_approximation.pdf) by Nguyen and Onak gives a lot of examples of random constant time approximation schemes: Maximum Matching (the running time depends only on the maximum degree of the graph), Set cover, etc. The authors present a method to design such algorithms.


---

### Answer by username_1 on 2015-10-13. Score: 5

There are many examples of games studied in combinatorial game theory where the state of a game can be described by a constant number of integer values. For some of these, a winning strategy for the game can be computed in constant time. But they also raise questions about what exactly your model of computation is.

One of the simplest and most basic combinatorial games is nim: one has a constant number of piles of beans, and in a single move you can remove any number of beans from one pile, either winning or losing (depending on your choice of rules) if you take the last bean. The optimal strategy can be computed in constant time if you allow bitwise Boolean xor operations (i.e. the ^ operator in programming languages like C/C++/Java/etc.) Is this a constant time algorithm in your model?

Here's one where it is known that there exists a constant time exact deterministic algorithm (in a possibly-unrealistic extended model of computation that allows you to test primality of a number in constant time) but it's not known what that algorithm is: given a starting move in the game of [Sylver coinage](https://en.wikipedia.org/wiki/Sylver_coinage), determine whether it is a winning or losing move. A flowchart for this problem is given in Berlecamp, Conway, and Guy, *Winning Ways*, but it depends on a finite set of counterexamples to a general characterization of the winning moves, and it's not known what that set is (or even whether it is empty).

Another interesting example from combinatorial game theory is [Wythoff's game](https://en.wikipedia.org/wiki/Wythoff%27s_game). Each game position can be described by a pair of integers (i.e., constant space, in your model of computation), moves in the game involve reducing one of these two integers to a smaller value, and the winning strategy involves moving to a position where the ratio between these two integers is as close to the golden ratio as possible. But in many game positions there is a choice: you can reduce the larger of the two integers either to the point where it is (nearly) the smaller integer times the golden ratio, or the smaller integer divided by the golden ratio. Only one of these two choices will be a winning move. So the optimal strategy can be defined in terms of a constant number of arithmetic operations, but these operations involve an irrational number, the golden ratio. Is that a constant time algorithm in your model? Maybe it's an example of non-uniform constant time, where the algorithm is constant time if it is given access to a constant amount of extra "hint" information that depends on $n$ (an approximation to the golden ratio accurate to $\log n$ bits) but not constant time using only arithmetic operations (no square roots) and fixed integer constants values?

> **Comments:**
> **username_0**: Thank you, these are all interesting examples. They also nicely shed light to the fact that the concept of "constant time" is less clear than I originally thought...  

---

