# What are some problems where we know we have an optimal algorithm?

What are some non-trivial problems where we know the current algorithm we have is the asymptotically optimal one? (For turing machines)

And how is this proved?

• A turing machine is a tricky model for lower bounds. Changing the defn can change the polynomial in the running time, so you need to be a little more specific. Jan 22 '12 at 2:13
• How do you define non-trivial? Jan 24 '12 at 8:03
• As says Suresh, the kind of TM you use has an influence. I guess that for the language of palindromes (words you can read backwards), we have an optimal 1-tape TM which takes $\mathcal O(n^2)$ steps to decide the language. And for 2-tape TMs, it is decidable in linear time, thus pretty much optimal too. Jun 27 '12 at 6:41
• Jun 27 '12 at 21:26

Any algorithm which takes linear time and has to read its whole input must be asymptotically optimal. Similarly, as Raphael comments, any algorithm whose runtime is of the same order as output size is optimal.

• Similarly, any algorithm whose runtime is of the same order as output size is optimal. Jan 21 '12 at 16:57
• I believe this answer and the comment that follows it are the complete state of the art. Jan 22 '12 at 18:35
• Well this was dissapointing Jan 23 '12 at 5:56
• For the record, JɛﬀE's comment seems to refer to Shir's answer below. Jun 23 '13 at 14:17
• I was referring to Max's answer, not Shir's, and to Raphael's comment on Max's answer. Mar 15 '14 at 22:32

If the complexity measure you are considering is query complexity, i.e., the number of times the machine has to look at the input to solve a particular problem, then there are many problems for which we have optimal algorithms. The reason for this is that lower bounds for query complexity are easier to achieve than lower bounds for time or space complexity, thanks to some popular techniques including the adversary method.

The downside, however, is that this complexity measure is almost excusively used in quantum information processing as it provides an easy way of proving a gap between quantum and classical computational power. The most notorious quantum algorithm in this framework is Grover's algorithm. Given a binary string $x_1,\dots ,x_n$ for which there exists a single $i$ such that $x_i=n$, you are required to find $i$. Classically (without a quantum computer), the most trivial algorithm is optimal: you need to query this string $n/2$ times on average in order to find $i$. Grover provided a quantum algorithm that does so in $O(\sqrt n)$ queries to the string. This has also been proven optimal.

• Indeed, query complexity is the underlying basis for Max's answer. For most problems, any algorithm provably "has to read the entire input" or at least a constant fraction of the input. Jan 24 '12 at 10:14
• Query complexity is also the basis of the study of evasiveness of (computing) graph properties. Apr 23 at 14:34
• If you are willing to change your model, quite a few lower bounds in data structures are tight. See Lower Bounds for Data Structures for pointers to good references for lower bounds in data structures.
• From the $$\Omega(n \log n)$$ bound for sorting in the comparison model that some people have mentioned here, you can obtain a similar bound for the convex hull problem by considering the case where the input is composed of points along the graph of an increasing function in the first quadrant of the plane.
• +1 for mentioning data structures. But I don't think it's possible to obtain a useful lower bound for convex hulls via the comparison lower bounds for sorting. The reason is that the comparison model isn't powerful enough to compute convex hulls at all. What works instead is to use a more powerful model such as algebraic decision trees in which hulls can be computed, and then to adapt the lower bound for sorting to this more powerful model. Jan 24 '12 at 21:20
• Makes sense, thanks for the clarification! Jan 27 '12 at 9:20

Suppose you are given input $w = \langle M, x, t \rangle$ and are asked to decide if RAM machine $M$ terminates on input $x$ after $t$ steps. By the time hierarchy theorem, the optimal algorithm to decide this is to simulate the execution of $M(x)$ for $t$ steps, which can be done in time $O(t)$.

(Note: for Turing machines, simulating the execution of $M$ takes $O(t \log t)$ steps; we only know a lower bound of $\Omega(t)$. So, this is not quite optimal for Turing machines specifically).

There are some other problems which contain the version of the halting problem as a sub-case. For example, deciding whether a sentence $\theta$ is a consequence of the WS1S takes time $2 \uparrow \uparrow O(|\theta|)$ and this is optimal.

I am unsure what you mean by "non-trivial", but how about this. $L = \{0^{2^k} | k \geq 0\}$. This language is not regular therefore, any TM deciding it must run in $\Omega(n \log n)$. The simple algorithm (crossing every other 0) is optimal.

If you allow dynamic data structure problems, we know some super-linear time optimal algorithms. This is in the cell probe model, which is as strong as the word RAM, i.e. this is not a restricted model such as algebraic decision trees.

One example is keeping prefix sums under dynamic updates. We start with an array of numbers $A[1], \ldots, A[n]$, and the goal is to keep a data structure that allows the following operations:

• Add $\Delta$ to $A[i]$, given $i$ and $\Delta$
• Compute the prefix sum $\sum_{j = 1}^i{A[i]}$, given $i$

You can easily support both operations in $O(\log n)$ time with a data structure based on an augmented binary tree with $A[i]$ at the leaves. Patrascu and Demaine showed this is optimal: for any data structure there is a sequence of $n$ additions and prefix sum queries that must take $\Omega(n\log n)$ time total.

Another example is union find: start with a partition of $\{1, \ldots n\}$ into singletons, and keep a data structure that allows the two operations:

• Union: given $i$ and $j$, replace the part containing $i$ and the part containing $j$ with their union
• Find: given $i$, output a canonical element from the part containing $i$

Tarjan showed that the classical disjoint set forest data structure with the union by rank and path compression heuristics takes $O(\alpha(n))$ time per operation, where $\alpha$ is the inverse Ackermann function. Fredman and Saks showed this is optimal: for any data structure there exists a sequence of $n$ union and find operations which must take $\Omega(n\alpha(n))$ time.

Breaking news! A fresh result dating back to Monday:

The Petri net reachibility problem was shown to have an Ackermannian lower bound (paper), which matches the complexity of the best known algorithm. Thus, the latter algorithm is optimal (if one ignores some function in the complexity that is much smaller than Ackermann, making the difference between Turing and RAM models complexity negligible).

I don't resist the temptation to told how I knew this result, because I think that is funny. When reading this question on Monday, I remembered the result by Jérôme Leroux and his coauthors (STOC 2019 best paper) that the problem is not in ELEMENTARY. So I asked him what is the current gap between the lower and upper bounds. He replied "I'm writing the proof that the lower bound is Ackermannian too. It will be on arXiv in few hours. So wait until tomorrow to post your response".

According to the paper on arXiv, a much simpler proof by Wojciech Czerwinski and Lukasz Orlikowski will be soon available.

• The Czerwiński–Orlikowski paper is already available: arxiv.org/abs/2104.13866 . Apr 29 at 12:11
• @EmilJeřábek Ah ok. Jérôme was not yet aware of that at noon :) It was posted yesterday. Apr 29 at 14:15
1. Comparison sorting using $O (n \log n)$ comparisons (merge sort, to name one) is optimal, the proof involves simply calculating the height of a tree with $n!$ leaves.

2. Assuming the Unique Games Conjecture, Khot, Kindler, Mossel and O'donnell showed that it is NP-complete to approximate Max-Cut better than Goemans and Williamson's algorithm. So in that sense G&W is optimal (assuming also that $P\neq NP$).

3. Some distributed algorithms can be shown to be optimal with respect to some conditions (e.g., the proportion of adversarial processors), but since you mentioned Turing machines, I guess that's not the type of examples you're looking for.

• Whether item 2 answers the question or not depends on what the asker means by “optimal,” although I doubt that the asker is asking in that sense (otherwise there are many, many tight approximability results which do not even require UGC). Moreover, I do not think that either item 1 or 3 answers the question. Jan 21 '12 at 16:31
• @TsuyoshiIto, it's hard to guess what exactly the asker meant, which is what made me try answers in various directions in hope of hitting something useful for him/her. What makes you say that (1) is not a valid answer, by the way?
– Shir
Jan 21 '12 at 16:34
• The asker specifically asks an algorithm optimal for Turing machine. Jan 21 '12 at 20:21
• Is "comparison sorting" actually a "problem"? Or is it a problem and a restriction on the model of computation? Jan 22 '12 at 18:36

The minimum spanning tree problem has an algorithm that was proven to be optimal by Pettie and Ramachandran, and they did so by essentially brute forcing decision trees corresponding to MSTs, and using them to construct the actual MST. However, the runtime is unknown, other than the fact that it is optimal.

• Can you make the citation slightly more detailed?
– usul
Apr 24 at 19:18

Many streaming algorithms have upper bounds matching their lower bounds.

For this question, Levin's universal search should be mentioned somewhere. This is an algorithm that is constant-factor optimal for some problems, although we generally do not know which problems nor how fast it runs.

The idea is to dovetail the computations of all possible Turing machines, weighted by $$\exp(-$$ description length $$)$$, checking each possible output, until a solution is found. This algorithm will be optimal up to a constant factor (the constant is around $$\exp($$ description length $$)$$) under a few conditions: it is faster to verify a solution than to find one, and either a solution is guaranteed to exist or one also has a fast verifier of proofs that a solution does not exist.

I like this writeup: https://steemit.com/steemstem/@markgritter/leonid-levin-s-universal-algorithm

there are two somewhat similar search algorithms that [my understanding is] are optimal based on a particular constraints on the input ordering/distribution. however presentations of the algorithms do not typically emphasize this optimality.

• golden section search for finding the maximum or minimum (extremum) of a unimodal function. assumes input is a unimodal function. finds it in logarithmic time on average. as I recall there may have been a proof of optimality in the book Structure & Interpretation of computer programs by abelson & sussman.

• binary search finds a point in logarithmic time on average in a sorted list, but requires input to be sorted.

am citing wikipedia above but it does not have the proofs that they are optimal, maybe some other references that prove optimality can be found by the audience.

Many sublinear time algorithms have upper bounds matching their lower bounds.

• Flagged as a duplicate. Jan 24 '12 at 10:09
• Sublinear time algorithm and streaming algorithm are different areas. Jan 24 '12 at 15:09
• That's true, but you should combine the answers into one. Jan 24 '12 at 22:37
• Some examples of optimal sublinear time algorithms can be Jan 25 '12 at 16:05
• it is also not clear why this is not a duplicate of the query complexity answer. Jan 26 '12 at 16:39