Decision problem such that any algorithm admits an exponentially faster algorithm

Question

In Hromkovič's Algorithmics for Hard Problems (2nd edition) there is this theorem (2.3.3.3, page 117):

There is a (decidable) decision problem $P$ such that for every algorithm $A$ that solves $P$ there is another algorithm $A'$ that also solves $P$ and additionally fulfills
$\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

$\mathrm{Time}_A(n)$ is the worst-case runtime of $A$ on inputs of size $n$ and $\forall^\infty$ means "for all but finitely many".

A proof is not given and we have no idea how to go about this; it is quite counter-intuitive, actually. How can the theorem be proven?

• Charles: For the title, maybe something like: "Is there a decision problem for which any solving algorithm can be improved?" That being said, it's just a shot in the dark, but couldn't it be the case that it's a degenerate case for a trivial decision problem? Somehow, if you turn the equality around, it means that it's always possible to solve a problem in a "worst" way (by doing useless steps). But that's just a guess.

Answer 1

It seems to be a simple case of Blum's Speedup Theorem:

Given a Blum complexity measure $(\varphi, \Phi)$ and a total computable function $f$ with two parameters, then there exists a total computable predicate $g$ (a Boolean valued computable function) so that for every program $i$ for $g,ドル there exists a program $j$ for $g$ so that for almost all $x$ $$f(x,\Phi_j(x)) \leq \Phi_i(x)$$

Just let the the complexity measure be the time complexity measure (i.e. $\Phi_e(x)$ is the time complexity of the Turing machine with code $e$) and let $f(x,y) = 2^y$.

• Aryabhata: +1: Here is a link to the original paper: logic.cse.unt.edu/tarau/teaching/SoftEng/OLD/papersToDiscuss/….