Problem decyzyjny taki, że dowolny algorytm dopuszcza wykładniczo szybszy algorytm

W Hromkovič's Algorytmics for Hard Problems (2nd edition) znajduje się takie twierdzenie (2.3.3.3, strona 117):

Istnieje (rozstrzygalny) problem decyzyjny taki że dla każdego algorytmu A, który rozwiązuje P, istnieje inny algorytm A ', który również rozwiązuje P i dodatkowo spełnia$P$$A$$P$$A'$$P$
$\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

jest najgorszym przypadku czas pracyAna wejściach wielkościni ∀ ∞ oznacza „dla wszystkich z wielu skończenie”.$\mathrm{Time}_A(n)$$A$$n$$\forall^\infty$

Nie podano dowodu i nie mamy pojęcia, jak sobie z tym poradzić; w rzeczywistości jest to dość sprzeczne z intuicją. Jak udowodnić to twierdzenie?

Wydaje się, że jest to prosty przypadek twierdzenia Bluma o przyspieszeniu :

$(\varphi, \Phi)$$f$$g$$i$$g$$j$$g$$x$

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

$\Phi_e(x)$$e$$f(x,y) = 2^y$