12
$\begingroup$

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?

Improve this question
$\endgroup$
9
  • 6
    $\begingroup$ Does verifying a probabilistically checkable proof count? $\endgroup$
    – David Eppstein
    Commented Oct 11, 2015 at 6:30
  • 6
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Commented Oct 11, 2015 at 9:35
  • 4
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Commented Oct 11, 2015 at 9:37
  • 4
    $\begingroup$ 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. $\endgroup$
    – Jukka Suomela
    Commented Oct 11, 2015 at 11:38
  • 5
    $\begingroup$ 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. $\endgroup$
    – J.-E. Pin
    Commented Oct 13, 2015 at 9:03

3 Answers 3

Reset to default
7
$\begingroup$

The paper Constant-Time Approximation Algorithms via Local Improvements 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.

Improve this answer
$\endgroup$
5
$\begingroup$

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, 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. 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?

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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... $\endgroup$
    – Andras Farago
    Commented Oct 14, 2015 at 2:03
1
$\begingroup$

If the prime decomposition of the order $|G|$ of a group $G$ is given and a prime $p$, than combining Cauchy's theorem and Lagrange's Theorem, than it can be checked in time $m$, where $m$ are the number of distinct prime divisors of $|G|$, if $G$ has an element of order $p$. Now it is clear, that this is not constant time if $m$ is variable, but if you try to naively find such an element, for example by trying all elements of $G$, then the time will be at least $|G|$. If $m$ is fixed than it is constant time, namely time $m$, which is constant because $m$ is fixed. On the other hand, if one is pedantic, than one can argue, that no constant time algorithm exists if the algorithm first has to read a variable-length input to make a decision.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.