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

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

• 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.

Answer 4

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.

Answer 5

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.

Answer 6

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.

Answer 7

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.

Answer 8

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.

Answer 9

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.

Answer 10

Many streaming algorithms have upper bounds matching their lower bounds.

Answer 11

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

Answer 12

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.}

Answer 13

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