Points to ponder:

Speedup theorem:

There exists a (total computable) predicate P such that for any algorithm computing P(x) with running time T(x), there exists another algorithm computing P(x) with computation time O(ln T(x)).

Gap theorem:

For any computable unbounded r(n) there exist a computable time bound t(n) such that any language
computable in time t(n) is also computable in time r(t(n)).

How do these results gel with our sense that problems should have intrinsic running times ? what’s the catch ?

Advertisements