# Consequences/existence of problems without any “optimal” algorithm

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?

• As far as we know, even SAT might not have an "optimal algorithm"... – Avi Tal Aug 22 at 1:54

Blum's 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 :).