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 który rozwiązuje istnieje inny algorytm który również rozwiązuje 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 pracyna wejściach wielkościi 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?

complexity-theory

— Raphael
źródło

W tytule może być coś takiego: „Czy istnieje problem decyzyjny, dla którego można ulepszyć dowolny algorytm rozwiązywania?” To powiedziawszy, to tylko strzał w ciemność, ale czy nie może być tak, że jest to zdegenerowany przypadek trywialnego problemu decyzyjnego? W jakiś sposób, jeśli odwrócisz równość, oznacza to, że zawsze można rozwiązać problem w „najgorszy” sposób (wykonując bezużyteczne kroki). Ale to tylko przypuszczenie.

— Charles

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

$(\varphi, \Phi)$ $f$ $g$ $i$ $g$ $j$ $g$ $x$
$f (x, Φ_{j} (x)) \leq Φ_{i} (x)$ $f(x,\Phi_j(x)) \leq \Phi_i(x)$

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

— Kaveh
źródło

+1: Tu jest link do oryginalnego papieru: logic.cse.unt.edu/tarau/teaching/SoftEng/OLD/papersToDiscuss/... .

— Aryabhata