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?

  • $\begingroup$ As far as we know, even SAT might not have an "optimal algorithm"... $\endgroup$
    – Avi Tal
    Aug 22 '19 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 :).

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


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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.