Problema de decisão, de modo que qualquer algoritmo admita um algoritmo exponencialmente mais rápido

Em Algorithmics for Hard Problems, de Hromkovič (2ª edição), existe este teorema (2.3.3.3, página 117):

Existe um problema de decisão (decidível) tal que, para todo algoritmo que resolve existe outro algoritmo que também resolve e cumpre adicionalmente $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)$ é o pior tempo de execução de em entradas de tamanho e significa "para todos, exceto muitos". $A$ $n$ $\forall^\infty$

Uma prova não é fornecida e não temos idéia de como fazer isso; é bastante contra-intuitivo, na verdade. Como o teorema pode ser provado?

complexity-theory Rafael
fonte

Para o título, talvez algo como: "Existe um problema de decisão para o qual qualquer algoritmo de solução pode ser aprimorado?" Dito isto, é apenas um tiro no escuro, mas não poderia ser o caso de um caso degenerado de um problema de decisão trivial? De alguma forma, se você inverte a igualdade, significa que sempre é possível resolver um problema da "pior maneira" (executando etapas inúteis). Mas isso é apenas um palpite.

Charles

Respostas:

Parece ser um caso simples do Teorema Speedup de Blum :

Dada uma medida de complexidade de Blum e uma função computável total com dois parâmetros, existe um predicado computável total (uma função computável com valor booleano), de modo que, para todo programa para , exista um programa para modo que, para quase todo $(\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)$

Apenas deixe a medida da complexidade ser a medida da complexidade do tempo (ie é a complexidade do tempo da máquina de Turing com o código ) e deixe . $\Phi_e(x)$ $e$ $f(x,y) = 2^y$

Kaveh
fonte

+1: Aqui está um link para o artigo original: logic.cse.unt.edu/tarau/teaching/SoftEng/OLD/papersToDiscuss/… .

Aryabhata