<p><a href="https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem" rel="noreferrer">Blum's speedup theorem</a>, proved in 1967, shows that there is such a problem <span class="math-container">$P$</span> that has no optimal algorithm.</p>

<p>The problem <span class="math-container">$P$</span> doesn't look all that much like addition or graph coloring - it's defined in terms of sets of machines <span class="math-container">$Z_i$</span>, the primitive recursive functions <span class="math-container">$\phi_i(n)$</span> computed by the <span class="math-container">$i$</span>th machine, and "step-counting functions" <span class="math-container">$\Phi_i(n)$</span> (which count how many steps the <span class="math-container">$i$</span>th machine took to execute its function), and involves search over the latter in order to achieve the desired properties :).</p>

<p>It's a good reminder that the space of algorithms is large and counterintuitive - especially when the inputs and outputs are themselves programs. But you're also not likely to see this sort of weirdness <em>until</em> your inputs are programs, either, and maybe not even then depending on what you're trying to do with them...</p>

<p>Reference:</p>

<p>Blum, Manuel. "A machine-independent theory of the complexity of recursive functions." <em>Journal of the ACM (JACM)</em> 14.2 (1967): 322-336.</p>

CC BY-SA 4.0
2019-08-21T03:43:02.830Z
2019-08-21T03:43:02.830Z
Will Angley
<p>Let <span class="math-container">$P$</span> be some kind of "problem" such as addition or graph coloring, that has an input size <span class="math-container">$n$</span>. Let <span class="math-container">$S_P$</span> denote the set of algorithms <span class="math-container">$A_1, A_2, \dots$</span> which deterministically solve <span class="math-container">$P$</span>. Based off this, let <span class="math-container">$S'_P$</span> denote the set of "optimal" algorithms that solve <span class="math-container">$P$</span>, in other words: </p>

<p><span class="math-container">$$S'_P :=  \{A_i ∈ S_P | \nexists A_j ∈ S_P  \textrm{ s.t.} \lim_{n \to \infty} \frac{O(A_i)}{O(A_j)} = 0 \}$$</span></p>

<p>Is there an example of a problem when <span class="math-container">$S_P$</span> is non-empty, but <span class="math-container">$S'_P = \emptyset$</span>? Also, are there any significant implications concerning the existence/non-existence of such a problem?</p>

CC BY-SA 4.0
2019-08-22T01:54:25.410Z
As far as we know, even SAT might not have an "optimal algorithm"...
Avi Tal
<ds.algorithms><complexity-classes><time-complexity>
Consequences/existence of problems without any "optimal" algorithm
Zach Hunter
# Consequences/existence of problems without any "optimal" algorithm

(Asked by: username_0 on 2019-08-20)

Let $P$ be some kind of "problem" such as addition or graph coloring, that has an input size $n$. Let $S\_P$ denote the set of algorithms $A\_1, A\_2, \dots$ which deterministically solve $P$. Based off this, let $S'\_P$ denote the set of "optimal" algorithms that solve $P$, in other words:

$$S'\_P := \{A\_i ∈ S\_P | \nexists A\_j ∈ S\_P \textrm{ s.t.} \lim\_{n \to \infty} \frac{O(A\_i)}{O(A\_j)} = 0 \}$$

Is there an example of a problem when $S\_P$ is non-empty, but $S'\_P = \emptyset$? Also, are there any significant implications concerning the existence/non-existence of such a problem?

**Tags:** ds.algorithms, complexity-classes, time-complexity
> **Comments:**
> **username_1**: As far as we know, even SAT might not have an "optimal algorithm"...  

---

## 1 answers

### Answer by username_2 on 2019-08-21. Score: 5 | Accepted answer

[Blum's speedup theorem](https://en.wikipedia.org/wiki/Blum%27s_speedup_theorem), proved in 1967, shows that there is such a problem $P$ that has no optimal algorithm.

The problem $P$ doesn't look all that much like addition or graph coloring - it's defined in terms of sets of machines $Z\_i$, the primitive recursive functions $\phi\_i(n)$ computed by the $i$th machine, and "step-counting functions" $\Phi\_i(n)$ (which count how many steps the $i$th machine took to execute its function), and involves search over the latter in order to achieve the desired properties :).

It's a good reminder that the space of algorithms is large and counterintuitive - especially when the inputs and outputs are themselves programs. But you're also not likely to see this sort of weirdness *until* your inputs are programs, either, and maybe not even then depending on what you're trying to do with them...

Reference:

Blum, Manuel. "A machine-independent theory of the complexity of recursive functions." *Journal of the ACM (JACM)* 14.2 (1967): 322-336.


---

