Problème de décision tel que tout algorithme admet un algorithme exponentiellement plus rapide

Dans Algorithmics for Hard Problems de Hromkovič (2e édition), il y a ce théorème (2.3.3.3, page 117):

Il existe un problème de décision (décidable) tel que pour chaque algorithme qui résout il existe un autre algorithme qui résout également et remplit en outreA P A ′$P$$A$$P$$A'$$P$
$\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

$\mathrm{Time}_A(n)$ est le pire cas d'exécution de $A$ sur des entrées de taille $n$ et $\forall^\infty$ signifie "pour tous mais en nombre infini".

Aucune preuve n'est donnée et nous n'avons aucune idée de la façon de procéder; c'est assez contre-intuitif, en fait. Comment prouver le théorème?

Il semble que ce soit un cas simple du théorème d'accélération de Blum :

Étant donné une mesure de complexité Blum et une fonction calculable totale avec deux paramètres, alors il existe un prédicat calculable total (une fonction calculable à valeur booléenne) de sorte que pour chaque programme pour , il existe un programme pour sorte que pour presque toutf g i g j g x f ( x , Φ j ( x ) ) ≤ Φ i ( x $(\varphi, \Phi)$$f$$g$$i$$g$$j$$g$$x$

$$f(x,\Phi_j(x)) \leq \Phi_i(x)$$

Soit simplement la mesure de complexité la mesure de complexité temporelle (ie est la complexité temporelle de la machine de Turing avec le code ) et soit .e f ( x , y ) = 2 $\Phi_e(x)$$e$$f(x,y) = 2^y$