P / poly NP / poly tem implicações interessantes?

12

P/poly=NP/poly implica , que por sua vez tem conseqüências interessantes como o colapso da hierarquia polinomial.NPP/poly

Existem implicações interessantes para ?P/polyNP/poly

Thomas Klimpel
fonte
6
P/poly=NP/poly é equivalente a . NPP/poly
Emil Jeřábek 3.0 26/06
1
@ EmilJeřábek Então você diz P / poly NP / poly implica NP P / poly. Você tem alguma referência para isso ou pode me explicar como ver isso? Se sim, então isso definitivamente se qualifica como uma resposta.
Thomas Klimpel
5
@ Kaveh: está removendo a motivação realmente o tipo de coisa que deveríamos estar fazendo? Ele me apresentou coisas que eu nunca havia encontrado antes, e não é como se não tivesse sido cortada. Este não é o Twitter.
András Salamon
4
@ EmilJeřábek Acho que entendi agora. NP P / poly implica P / poly = NP / poly, porque o algoritmo determinístico pode obter sua própria sequência de aconselhamento para se tornar tão poderoso quanto NP, junto com a sequência de aconselhamento para o idioma de NP / poly, e isso é o suficiente para decidir esse idioma.
Thomas Klimpel
2
@ThomasKlimpel: Sim, exatamente.
Emil Jeřábek 3.0

Respostas:

10

O comentário de Emil Jeřábek responde à pergunta:

P / poli NP / poli é equivalente a NP P / poli=

Observe o corolário

P / poli NP / poli implica P NP.

Prova de corolário:

  1. P / poli NP / poli é equivalente a NP P / poli (comentário de Emil)= 
  2. NP P / poli implica P / poli NP / poli (implícito em 1.)= 
  3. P / poli NP / poli implica NP P / poli (equivalente a 2.) 
  4. NP P / poli implica P NP (P P / poli) 
  5. P / poli NP / poli implica P NP (implicado em 3. e 4.) 

Prova do comentário de Emil: É suficiente mostrar que NP P / poli implica P / poli NP / poli.=

  1. Então, vamos assumir NP P / poly.
  2. Como SAT NP existe e uma sequência de strings de aconselhamento com , um algoritmo determinístico que pode decida instâncias SAT de tamanho in time , se tiver acesso a . WLOG, esse algoritmo também pode decidir instâncias SAT de tamanho , porque podemos definir uma sequência modificada com , onde todas as strings de conselhos anteriores estão incluídas em .pSATkSAT>0sn|sn|nkSATnnpSATsnnsn=sn1sn|sn|nkSAT+1sn
  3. Agora vamos NP / poly ser uma linguagem arbitrária, para a qual precisamos mostrar P / poly. Existe e uma sequência de conselhos com e um algoritmo não determinístico que pode decidir instâncias de tamanho em tempo , se tiver acesso a .LLpLkL>0ln|ln|nkLLnnpLln
  4. Para cada com , uma instância de SAT de tamanho pode ser computada (em tempo ) que pode ser satisfeita exatamente se .w|w|=ncnpLO(npL)wL
  5. Portanto, para a sequência de strings de aconselhamento com , a combinação dos algoritmos determinísticos de 2. e 4. fornece um algoritmo determinístico que pode decidir instâncias de tamanho no tempo , se tiver acesso a .tn=lnscnpL|tn|nkL+(cnpL)kSATLnO((cnpL)pSAT)tn
  6. Como NP / poly era uma linguagem arbitrária, isso mostra NP / poly P / poly, sob a suposição de que NP P / poly.L

Todas as provas acima são relativizadas, porque a existência de problemas completos de NP também é verdadeira em mundos relativizados. Isso sugere que é inútil procurar uma prova de que P / poly NP / poly. No entanto, vamos resumir a seção de motivação removidada pergunta como "A sequência de conselhos poderia ser um sistema axiomático formal (garantido automaticamente para ser consistente, sorriso maligno) cuja força está aumentando rapidamente com o comprimento da entrada, e NP é extremamente bom em explorar esse conselho". Se não se tomar muito cuidado com o fato de que "a existência de uma sequência de conselhos" apenas tenha significado "formal" em relação a um sistema formal fixo, é provável que essa configuração permita a construção de aparentes paradoxos. Mas a construção de tais paradoxos pode ser divertida, no entanto, e talvez eles até sugiram maneiras de construir provas de independência (para sistemas formais suficientemente fracos).

Thomas Klimpel
fonte