<p>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 <a href="http://cstheory.blogoverflow.com/tag/query-complexity/">adversary method</a>. </p>

<p>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 <a href="http://en.wikipedia.org/wiki/Grover%27s_algorithm">Grover's algorithm</a>. 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.</p>

CC BY-SA 3.0
2012-01-24T10:14:13.190Z
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.
Jeffε
CC BY-SA 4.0
2021-04-23T14:34:40.923Z
Query complexity is also the basis of the study of [evasiveness of (computing) graph properties](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=evasiveness+of+graph+properties).
Neal Young
CC BY-SA 3.0
2012-01-23T17:38:11.187Z
2012-01-23T17:38:11.187Z
lamontap
<ul>
<li>If you are willing to change your model, quite a few lower bounds in data structures are tight. See <a href="https://cstheory.stackexchange.com/questions/5517/lower-bounds-for-data-structures">Lower Bounds for Data Structures</a> for pointers to good references for lower bounds in data structures.</li>
<li>From the <span class="math-container">$\Omega(n \log n)$</span> 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.</li>
</ul>

CC BY-SA 3.0
2012-01-24T21:20:37.447Z
+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.
David Eppstein
CC BY-SA 3.0
2012-01-27T09:20:08.727Z
Makes sense, thanks for the clarification!
Abel Molina
CC BY-SA 4.0
2012-01-24T07:39:11.330Z
2021-04-23T08:33:31.670Z
2021-04-23T08:33:31.670Z
Abel Molina
<p>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.</p>

CC BY-SA 3.0
2012-06-27T16:33:06.520Z
2012-06-27T16:33:06.520Z
aelguindy
<p><strong>Breaking news!</strong> A fresh result dating back to Monday:</p>
<blockquote>
<p>The <a href="https://en.wikipedia.org/wiki/Petri_net#Reachability" rel="nofollow noreferrer">Petri net reachibility</a> problem was
shown to have an Ackermannian lower bound
(<a href="https://arxiv.org/abs/2104.12695" rel="nofollow noreferrer">paper</a>), 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).</p>
</blockquote>
<p>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 &quot;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&quot;.</p>
<p>According to the paper on arXiv, a much simpler proof by Wojciech Czerwinski and Lukasz Orlikowski will be soon available.</p>

CC BY-SA 4.0
2021-04-29T12:11:46.723Z
The Czerwiński–Orlikowski paper is already available: https://arxiv.org/abs/2104.13866 .
Emil Jeřábek
CC BY-SA 4.0
2021-04-29T14:15:17.460Z
@EmilJeřábek Ah ok. Jérôme was not yet aware of that at noon :) It was posted yesterday.
Lamine
CC BY-SA 4.0
2021-04-29T12:08:11.410Z
2021-04-29T12:08:11.410Z
Lamine
<p>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 <em>not</em> a restricted model such as algebraic decision trees.</p>

<p>One example is keeping <em>prefix sums</em> 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:</p>

<ul>
<li>Add $\Delta$ to $A[i]$, given $i$ and $\Delta$</li>
<li>Compute the prefix sum $\sum_{j = 1}^i{A[i]}$, given $i$</li>
</ul>

<p>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. <a href="http://dl.acm.org/citation.cfm?id=982796" rel="nofollow">Patrascu and Demaine</a> 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. </p>

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

<ul>
<li>Union: given $i$ and $j$, replace the part containing $i$ and the part containing $j$ with their union</li>
<li>Find: given $i$, output a canonical element from the part containing $i$</li>
</ul>

<p><a href="http://dl.acm.org/citation.cfm?id=321884" rel="nofollow">Tarjan</a> 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. <a href="http://dl.acm.org/citation.cfm?id=73040" rel="nofollow">Fredman and Saks</a> 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.</p>

CC BY-SA 3.0
2014-03-16T15:10:58.320Z
2014-03-16T15:10:58.320Z
Sasho Nikolov
<p>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)$.</p>

<p>(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).</p>

<p>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.</p>

CC BY-SA 3.0
2012-01-23T20:23:09.983Z
2012-01-24T13:34:20.617Z
2012-01-24T13:34:20.617Z
David Harris
<ol>
<li><p>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.</p></li>
<li><p>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&amp;W is optimal (assuming also that $P\neq NP$).</p></li>
<li><p>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.</p></li>
</ol>

CC BY-SA 3.0
2012-01-21T16:31:02.207Z
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.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-21T16:34:26.203Z
@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
CC BY-SA 3.0
2012-01-21T20:21:57.133Z
The asker specifically asks an algorithm optimal for _Turing machine_.
Tsuyoshi Ito
CC BY-SA 3.0
2012-01-22T18:36:26.397Z
Is "comparison sorting" actually a "problem"?  Or is it a problem *and* a restriction on the model of computation?
Jeffε
CC BY-SA 3.0
2012-01-21T14:59:04.743Z
2012-01-21T14:59:04.743Z
Shir
<p>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.</p>

CC BY-SA 4.0
2021-04-24T19:18:49.007Z
Can you make the citation slightly more detailed?
usul
CC BY-SA 4.0
2021-04-23T14:06:55.140Z
2021-04-23T14:06:55.140Z
user62077
<p>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.</p>
<p>The idea is to dovetail the computations of all possible Turing machines, weighted by <span class="math-container">$\exp(-$</span> description length <span class="math-container">$)$</span>, checking each possible output, until a solution is found. This algorithm will be optimal up to a constant factor (the constant is around <span class="math-container">$\exp($</span> description length <span class="math-container">$)$</span>) 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.</p>
<p>I like this writeup: <a href="https://steemit.com/steemstem/@markgritter/leonid-levin-s-universal-algorithm" rel="nofollow noreferrer">https://steemit.com/steemstem/@markgritter/leonid-levin-s-universal-algorithm</a></p>

CC BY-SA 4.0
2021-04-24T19:35:47.040Z
2021-04-24T19:35:47.040Z
usul
<p>Many streaming algorithms have upper bounds matching their lower bounds.</p>

CC BY-SA 3.0
2012-01-23T21:15:59.997Z
2012-01-23T21:15:59.997Z
Bin Fu
<p>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. </p>

<ul>
<li><p><a href="http://en.wikipedia.org/wiki/Golden_section_search" rel="nofollow">golden section search</a> 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 <a href="http://mitpress.mit.edu/sicp/full-text/book/book.html" rel="nofollow">Structure &amp; Interpretation of computer programs</a> by abelson &amp; sussman.</p></li>
<li><p><a href="http://en.wikipedia.org/wiki/Binary_search" rel="nofollow">binary search</a> finds a point in logarithmic time on average in a sorted list, but requires input to be sorted.</p></li>
</ul>

<p><sup>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.</sup></p>

CC BY-SA 3.0
2012-06-27T16:00:00.800Z
2012-06-27T16:00:00.800Z
vzn
<p>Many sublinear time algorithms have upper bounds matching their lower bounds.</p>

CC BY-SA 3.0
2012-01-24T10:09:27.723Z
Flagged as a duplicate.
Jeffε
CC BY-SA 3.0
2012-01-24T15:09:38.823Z
Sublinear time algorithm and streaming algorithm are different areas.
Bin Fu
CC BY-SA 3.0
2012-01-24T22:37:54.770Z
That's true, but you should combine the answers into one.
Suresh Venkat
CC BY-SA 3.0
2012-01-25T16:05:52.480Z
Some examples of optimal sublinear time algorithms can be
Bin Fu
CC BY-SA 3.0
2012-01-25T16:06:44.880Z
found in Chazelle, Liu and Magen's paper http://www.cs.princeton.edu/~dingliu/papers/stoc03.pdf. Bin Packing is another example.
Bin Fu
CC BY-SA 3.0
2012-01-26T16:39:19.463Z
it is also not clear why this is not a duplicate of the query complexity answer.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-23T20:30:16.033Z
2012-01-23T20:30:16.033Z
Bin Fu
<p>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.</p>

CC BY-SA 3.0
2012-01-21T16:57:42.397Z
Similarly, any algorithm whose runtime is of the same order as output size is optimal.
Raphael
CC BY-SA 3.0
2012-01-22T18:35:43.437Z
I believe this answer and the comment that follows it are the complete state of the art.
Jeffε
CC BY-SA 3.0
2012-01-23T00:06:59.587Z
@JɛﬀE, don't we have some non-trivial optimal circuit lowerbounds? (well, as Suresh said, it depends on what we mean by optimal, e.g. are we going to ignore constants?) On the other hand, we have [speed-up theorems](http://en.wikipedia.org/wiki/Speedup_theorem).
Kaveh
CC BY-SA 3.0
2012-01-23T05:56:32.323Z
Well this was dissapointing
sture
CC BY-SA 3.0
2012-06-27T21:26:00.920Z
Ironically, when I gave this same, trivial answer on the mathoverflow question *(see above)*, I got 0 upvotes :)
BlueRaja - Danny Pflughoeft
CC BY-SA 3.0
2013-06-23T14:17:05.263Z
For the record, JɛﬀE's comment seems to refer to Shir's answer below.
András Salamon
CC BY-SA 3.0
2014-03-15T21:58:30.700Z
@JɛﬀE: could you clarify whether your comment refers to Shir's answer or Raphael's comment?
Max
CC BY-SA 3.0
2014-03-15T22:32:16.493Z
I was referring to Max's answer, _not_ Shir's, and to Raphael's comment on Max's answer.
Jeffε
CC BY-SA 3.0
2012-01-21T14:17:21.663Z
2014-03-16T10:15:59.687Z
2014-03-16T10:15:59.687Z
Max
<p>What are some non-trivial problems where we know the current algorithm we have is the asymptotically optimal one? (For turing machines)</p>

<p>And how is this proved?</p>

CC BY-SA 3.0
2012-01-22T02:13:46.100Z
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.
Suresh Venkat
CC BY-SA 3.0
2012-01-24T08:03:12.373Z
How do you define non-trivial?
funkstar
CC BY-SA 3.0
2012-06-27T06:41:51.283Z
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.
Bruno
CC BY-SA 3.0
2012-06-27T21:26:18.377Z
See also http://mathoverflow.net/questions/31448/lower-bounds-in-theoretical-computer-science
BlueRaja - Danny Pflughoeft
<cc.complexity-theory><ds.algorithms><complexity-classes>
What are some problems where we know we have an optimal algorithm?
sture
# What are some problems where we know we have an optimal algorithm?

(Asked by: username_0 on 2012-01-21)

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?

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

> **Comments:**
> **username_1**: 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.  
> **username_2**: How do you define non-trivial?  
> **username_3**: 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.  
> **username_4**: See also http://mathoverflow.net/questions/31448/lower-bounds-in-theoretical-computer-science  

---

## 13 answers

### Answer by username_22 on 2012-01-21. Score: 20 | Accepted answer

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

> **Comments:**
> **username_23**: Similarly, any algorithm whose runtime is of the same order as output size is optimal.  
> **username_6**: I believe this answer and the comment that follows it are the complete state of the art.  
> **username_24**: @JɛﬀE, don't we have some non-trivial optimal circuit lowerbounds? (well, as Suresh said, it depends on what we mean by optimal, e.g. are we going to ignore constants?) On the other hand, we have [speed-up theorems](http://en.wikipedia.org/wiki/Speedup_theorem).  
> **username_0**: Well this was dissapointing  
> **username_4**: Ironically, when I gave this same, trivial answer on the mathoverflow question *(see above)*, I got 0 upvotes :)  
> **username_25**: For the record, JɛﬀE's comment seems to refer to username_15's answer below.  
> **username_22**: @JɛﬀE: could you clarify whether your comment refers to username_15's answer or username_23's comment?  
> **username_6**: I was referring to username_22's answer, _not_ username_15's, and to username_23's comment on username_22's answer.  

---

### Answer by username_5 on 2012-01-23. Score: 8

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](http://cstheory.blogoverflow.com/tag/query-complexity/).

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](http://en.wikipedia.org/wiki/Grover%27s_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.

> **Comments:**
> **username_6**: Indeed, query complexity is the underlying basis for username_22's answer.  For most problems, any algorithm provably "has to read the entire input" or at least a constant fraction of the input.  
> **username_7**: Query complexity is also the basis of the study of [evasiveness of (computing) graph properties](https://scholar.google.com/scholar?hl=en&as_sdt=0%2C22&q=evasiveness+of+graph+properties).  

---

### Answer by username_8 on 2012-01-24. Score: 6

* If you are willing to change your model, quite a few lower bounds in data structures are tight. See [Lower Bounds for Data Structures](https://cstheory.stackexchange.com/questions/5517/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.

> **Comments:**
> **username_9**: +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.  
> **username_8**: Makes sense, thanks for the clarification!  

---

### Answer by username_10 on 2012-06-27. Score: 4

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 by username_11 on 2021-04-29. Score: 4

**Breaking news!** A fresh result dating back to Monday:

> The [Petri net reachibility](https://en.wikipedia.org/wiki/Petri_net#Reachability) problem was
> shown to have an Ackermannian lower bound
> ([paper](https://arxiv.org/abs/2104.12695)), 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.

> **Comments:**
> **username_12**: The Czerwiński–Orlikowski paper is already available: https://arxiv.org/abs/2104.13866 .  
> **username_11**: @EmilJeřábek Ah ok. Jérôme was not yet aware of that at noon :) It was posted yesterday.  

---

### Answer by username_13 on 2014-03-16. Score: 4

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](http://dl.acm.org/citation.cfm?id=982796) 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](http://dl.acm.org/citation.cfm?id=321884) 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](http://dl.acm.org/citation.cfm?id=73040) 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 by username_14 on 2012-01-23. Score: 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 by username_15 on 2012-01-21. Score: 3

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

> **Comments:**
> **username_16**: 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.  
> **username_15**: @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?  
> **username_16**: The asker specifically asks an algorithm optimal for _Turing machine_.  
> **username_6**: Is "comparison sorting" actually a "problem"?  Or is it a problem *and* a restriction on the model of computation?  

---

### Answer by username_17 on 2021-04-23. Score: 2

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.

> **Comments:**
> **username_18**: Can you make the citation slightly more detailed?  

---

### Answer by username_18 on 2021-04-24. Score: 1

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 by username_19 on 2012-01-23. Score: 1

Many streaming algorithms have upper bounds matching their lower bounds.


---

### Answer by username_20 on 2012-06-27. Score: 0

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](http://en.wikipedia.org/wiki/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](http://mitpress.mit.edu/sicp/full-text/book/book.html) by abelson & sussman.
* [binary search](http://en.wikipedia.org/wiki/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 by username_19 on 2012-01-23. Score: -1

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

> **Comments:**
> **username_6**: Flagged as a duplicate.  
> **username_19**: Sublinear time algorithm and streaming algorithm are different areas.  
> **username_1**: That's true, but you should combine the answers into one.  
> **username_19**: Some examples of optimal sublinear time algorithms can be  
> **username_19**: found in Chazelle, Liu and Magen's paper http://www.cs.princeton.edu/~dingliu/papers/stoc03.pdf. Bin Packing is another example.  
> **username_21**: it is also not clear why this is not a duplicate of the query complexity answer.  

---

