Problema de decisión tal que cualquier algoritmo admite un algoritmo exponencialmente más rápido

En Algorithmics for Hard Problems de Hromkovič (2a edición) existe este teorema (2.3.3.3, página 117):

Hay un problema de decisión (decidible) tal que para cada algoritmo que resuelve hay otro algoritmo que también resuelve y además cumple $P$ $A$ $P$ $A'$ $P$
$\qquad \forall^\infty n \in \mathbb{N}. \mathrm{Time}_{A'}(n) = \log_2 \mathrm{Time}_A(n)$

es el tiempo de ejecución del peor caso deen entradas de tamañoy significa "para todos, pero un número finito". $\mathrm{Time}_A(n)$ $A$ $n$ $\forall^\infty$

No se proporciona una prueba y no tenemos idea de cómo hacerlo; Es bastante contra-intuitivo, en realidad. ¿Cómo se puede probar el teorema?

complexity-theory Rafael
fuente

Para el título, tal vez algo así como: "¿Hay algún problema de decisión para el que se pueda mejorar algún algoritmo de resolución?" Dicho esto, es solo un tiro en la oscuridad, pero ¿no podría ser el caso de que sea un caso degenerado para un problema de decisión trivial? De alguna manera, si cambia la igualdad, significa que siempre es posible resolver un problema de la "peor" manera (haciendo pasos inútiles). Pero eso es solo una suposición.

Charles

Respuestas:

Parece ser un caso simple del teorema de aceleración de Blum :

$(\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
fuente

+1: Aquí hay un enlace al documento original: logic.cse.unt.edu/tarau/teaching/SoftEng/OLD/papersToDiscuss/… .

Aryabhata