Comment by openasocket

It’s been a while since I studied complexity theory, but is that what Blums speed up theorem says? A quick google search suggests it states that there exist computable functions where there is no optimal program that computes it.

Like, there exist problems that have a lower bound of n time where algorithms can get arbitrarily close to O(n) complexity but there is no program that actually reaches it (there is one that runs in time O(n^{1.1}), one that runs in O(n^{1.01}), etc).

But that doesn’t mean that there aren’t hard walls, it just means there are hard walls where every program’s runtime is > that wall, rather than >= that wall. But maybe I’m misunderstanding, or there are some corollaries I’m missing?

As an aside, as someone who studied more on the pure math side, Blums speed up theorem is rather intuitive. It looks like there might be a relatively elegant proof using topology. Blums speed up theorem is basically just a statement that the set of programs that implement a particular computable function doesn’t satisfy the greatest lower bound property. This is also the case for, for example, the set of rational numbers: there exist subsets of the rational numbers with a lower bound but not a greatest lower bound (like the set of all positive rational numbers q where q^2 >= 2). I’m hand waving, but I think in that same vein you can show that the set of programs under the topology of ordering by runtime is completely disconnected.