In his Quantum Computing Since Democritus, Scott Aaronson outlined a proof sketch of Blum's Speedup Theorem which roughly looks like the following.

Given an enumeration of Turing Machines $\{M\}_{i \in \mathbb{N}}$. Let $S_i = \{M_1, ..., M_i\}$. We can construct a computable function $f(n)$ such that if $f(n)$ can be computed in $O(2^n)$ steps then it can also be computed in $O(2^{n-1})$ in the following manner (Python pseudocode):

canceled = set()
for i in range(n):
    for Mj in Si:
        if Mj not in canceled and Mj halts in 2 ** (n-i) steps:
            f(i) = 1 - output of Mj
     f(i) = 0
return f(n)           

Aaronson claims we can "hardwire" the canceled Turing Machines from iteration 1 to i and skip to iteration i+1. The complexity goes from $O(n^2 2^n)$ to $O(n^2 2^{n-i})$.

Why is this a valid argument? Wouldn't a similar argument "we can cache all the results" turn every computable function into $O(1)$?

Reference: https://www.scottaaronson.com/democritus/lec5.html


1 Answer 1


You cannot "cache all the results" because your program (or description of Turing machine) would need to be infinite. You can only cache a fixed number of results. In your example $i$ needs to be fixed. You cannot pick, e.g., $i=\frac{n}{2}$ and lower the complexity from $O(n^2 2^n)$ to $O(n^2 2^{n/2})$.

On an unrelated note $O(2^n)$ and $O(2^{n-1})$ are exactly the same set of functions so it is trivially true that a function that can be computed in time $O(2^n)$ can also be computed in time $O(2^{n-1})$ (or in time $O(2^{n-i})$ for any constant $i$).

The claim in the linked notes is stronger as it work for any complexity bound $t$. You need to pick a $t$ that grows quick enough to get something useful. In the notes $t$ is defined recursively as $t(n)= 2^{t(n-1)}$ which (assuming $t(0)=0$) corresponds to the power tower function that grows as $1, 2, 2^2,2^{2^2}, 2^{2^{2^2}}$, etc.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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