Solucionadores ideais de NP

12

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 ) LX{0,1}×{0,1}LXPxPyPXtP(n)tL(n)L

tL(n)<2|P|p(tP(n))

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

M { 0 , 1 } Q X M t M Q ( n ) t M L ( n ) L MLA 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 satisfazM{0,1}QXMtQM(n)tLM(n)LM

tLM(n)<2|Q|q(n,tQM(n))

onde é um polinômio fixo. A diferença crucial é que t M Q ( n ) pode ser, por exemplo, polinomial, mesmo que P N PqtQM(n)PNP

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 |L2|Q|2|Q||Q|P=NPQX2|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 satisfazAXM{0,1}QXMtQM(n)tAM(n)AM

tAM(n)<f(|Q|)q(n,tQM(n))+g(|Q|)

onde é polinomial, f é subexponencial eg é arbitrárioqfg

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 ?fgfPNP

Vanessa
fonte

Respostas:

12

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

n

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

xn

  • QnO(ntQM(n))poly(n)

  • Qnn<2|Q|2nO(1)=22O(|Q|)

tAM(n)poly(n)tQM(n)+22O(|Q|).

f(n)g(n)ng(n)nf(n)n

Yury
fonte
2|Q|tQM(2|Q|)