Solucionadores ideais de NP

Corrija um problema de pesquisa completo do NP, por exemplo, o formulário de pesquisa do SAT. A pesquisa de Levin fornece um algoritmo para resolver que é ótimo em algum sentido. Especificamente, o algoritmo é "Execute todos os programas possíveis com a entrada , uma vez que algum retorne a resposta testa se está correto". É ótimo no sentido de que, dado um programa que resolve com complexidade de tempo , a complexidade de tempo de satisfaz L X P x P Y P X t P ( n ) t L ( n ) $X \subset \lbrace 0,1 \rbrace^* \times \lbrace 0,1 \rbrace^*$$L$$X$$P$$x$$P$$y$$P$$X$$t_P(n)$$t_L(n)$$L$

$$t_L(n) < 2^{|P|}p(t_P(n))$$

onde é um polinômio fixo que depende do modelo de computação preciso$p$

M ⊂ { 0 , 1 } ∗ Q X M t M Q ( n ) t M L ( n ) L $L$A otimização de pode ser formulada de uma maneira um pouco mais forte. Ou seja, para cada e um programa que resolve com a promessa no tempo , a complexidade de tempo de restrita às entradas em satisfaz$M \subset \lbrace 0,1 \rbrace^*$$Q$$X$$M$$t^M_Q(n)$$t_L^M(n)$$L$$M$

$$t_L^M(n) < 2^{|Q|}q(n, t^M_Q(n))$$

onde é um polinômio fixo. A diferença crucial é que t M Q ( n ) pode ser, por exemplo, polinomial, mesmo que P ≠ N $q$$t^M_Q(n)$$P \neq NP$

A óbvia "fraqueza" de é o grande fator 2 | Q | nesse limite. É fácil ver que, se houver um algoritmo que satisfaça um limite da mesma forma com 2 | Q | substituído por um polinômio em | Q | então P = N P . Isso ocorre porque podemos considerar Q como um programa que resolve uma determinada instância do X codificando a resposta. Da mesma forma, se 2 | Q | pode ser substituído por uma função subexponencial de | Q $L$$2^{|Q|}$$2^{|Q|}$$|Q|$$P = NP$$Q$$X$$2^{|Q|}$$|Q|$então a hipótese de tempo exponencial é violada. No entanto, a resposta à seguinte pergunta é menos óbvia (para mim):

Assumindo a hipótese do tempo exponencial e outras conjecturas conhecidas (por exemplo, não degeneração da hierarquia polinomial, existência de funções unidirecionais), se necessário, existe um algoritmo resolve X st para cada M ⊂ { 0 , 1 } ∗ e Q um programa que resolve X com a promessa M no tempo t M Q ( n ) , a complexidade do tempo t M A ( n ) de A restrita às entradas em M satisfaz$A$$X$$M \subset \lbrace 0,1 \rbrace^*$$Q$$X$$M$$t^M_Q(n)$$t_A^M(n)$$A$$M$

$$t_A^M(n) < f(|Q|)q(n, t^M_Q(n)) + g(|Q|)$$

onde é polinomial, f é subexponencial eg é arbitrário$q$$f$$g$

Se a resposta for positiva, pode ser polinomial? Qual é a taxa de crescimento de g (claramente pelo menos exponencial sob ETH)? Se a resposta for negativa, o polinômio f pode existir se ETH estiver errado, mas P ≠ N P ?$f$$g$$f$$P \neq NP$

Considere o seguinte algoritmo (uma variante do algoritmo de Levin):

$n$

Pare quando um dos algoritmos encontrar uma solução.

$x$$n$

• $Q$$n$$O(n \cdot t^M_Q(n)) \cdot \mathrm{poly}(n)$

• $Q$$n$$n < 2^{|Q|}$$2^{n^{O(1)}} = 2^{2^{O(|Q|)}}$

$$t^M_A(n) \leq \mathrm{poly}(n) \cdot t^M_Q(n) + 2^{2^{O(|Q|)}}.$$

$f(n)$$g(n)$$n$$g(n)$$n$$f(n)$$n$