Hat P / poly NP / poly interessante Implikationen?

12

P / P o l y = N P / p o l y N P P / p o l yP/poly=NP/poly impliziert , was wiederum interessante Konsequenzen wie den Zusammenbruch der Polynomhierarchie hat.NPP/poly

Gibt es interessante Implikationen für ?P / P o l y N P / p o l yP/polyNP/poly

Thomas Klimpel
quelle
6
P / P o l y = N P / p o l y N P P / p o l yP/poly=NP/poly ist äquivalent zu . NPP/poly
Emil Jeřábek unterstützt Monica am
1
@ EmilJeřábek Du sagst also P / poly NP / poly impliziert NP P / poly. Haben Sie eine Referenz dafür oder können Sie mir erklären, wie ich das sehe? Wenn ja, dann ist dies definitiv eine Antwort.
Thomas Klimpel
5
@Kaveh: Ist das Entfernen der Motivation wirklich das, was wir tun sollten? Es hat mich mit Dingen bekannt gemacht, denen ich vorher nicht begegnet bin, und es ist nicht so, als wäre es nicht abgespalten worden. Das ist nicht Twitter.
András Salamon
4
@ EmilJeřábek Ich glaube, ich habe es jetzt bekommen. NP P / poly impliziert P / poly = NP / poly, da der deterministische Algorithmus sowohl eine eigene Hinweiszeichenfolge für die Leistungsstärke von NP als auch eine Hinweiszeichenfolge für die Sprache von NP / poly erhalten kann genug, um diese Sprache zu entscheiden.
Thomas Klimpel
2
@ThomasKlimpel: Ja genau.
Emil Jeřábek unterstützt Monica am

Antworten:

10

Der Kommentar von Emil Jeřábek beantwortet die Frage:

P / poly NP / poly ist äquivalent zu NP P / poly= =

Beachten Sie die Folgerung

P / poly NP / poly impliziert P NP.

Beweis der Folgerung:

  1. P / poly NP / poly ist äquivalent zu NP P / poly (Emil's Kommentar)= =  
  2. NP P / poly impliziert P / poly NP / poly (impliziert durch 1.)==  
  3. P / poly NP / poly impliziert NP P / poly (äquivalent zu 2.)  
  4. NP P / poly impliziert P NP (P P / poly)& ne;   
  5. P / poly NP / poly impliziert P NP (impliziert durch 3. und 4.)  

Beweis von Emil's Kommentar: Es ist ausreichend zu zeigen, dass NP P / poly P / poly NP / poly impliziert .==

  1. Nehmen wir also NP P / poly an.
  2. Da SAT NP existiert, gibt es und eine Folge von mit , einem deterministischen Algorithmus, der dies kann Entscheide rechtzeitig über SAT-Instanzen der Größe , wenn sie Zugriff auf . WLOG, dieser Algorithmus kann auch SAT-Instanzen der Größe bestimmen, da wir mit eine modifizierte Sequenz definieren können. , wobei alle vorherigen in .p S A Tk S A T > 0 s n | s n | n k S A T n n p S A T s nn s ' n = s ' n - 1 s n | s ' n | n k S A T + 1 s 'pSATkSAT>0sn|sn|nkSATnnpSA Tsnnsn= sn - 1sn| sn| nkSA T+1nsn
  3. Nun sei NP / poly eine beliebige Sprache, für die wir P / poly zeigen müssen. Es gibt und eine Folge von mit und einen nicht deterministischen Algorithmus, der Instanzen der Größe in der Zeit bestimmen kann , wenn es Zugriff auf .L L p Lk L > 0 l n | l n | n k L L n n p L l nLLpLkL>0ln|ln|nkLLnnpLln
  4. Für jedes mit kann eine SAT-Instanz der Größe berechnet werden (in der Zeit ), die genau dann erfüllt werden kann, wenn .w | w | = N c n p L O ( n p L ) w Lw|w|=ncnpLO(npL)wL
  5. Also für die Folge von mit , Die Kombination der deterministischen Algorithmen aus 2. und 4. ergibt einen deterministischen Algorithmus, der Instanzen der Größe in der Zeit bestimmen kann , falls dies der Fall ist Zugriff auf .t n = l n s c n p L | t n | n k L + ( c n p L ) k S A T L n O ( ( c n p L ) p S A T ) t ntn=lnscnpL|tn|nkL+(cnpL)kSATLnO((cnpL)pSAT)tn
  6. Da NP / poly eine beliebige Sprache war, zeigt dies NP / poly P / poly unter der Annahme, dass NP P / poly.L L

Alle oben genannten Beweise relativieren sich, weil die Existenz von NP-vollständigen Problemen auch in relativierten Welten zutrifft. Dies legt nahe, dass es sinnlos ist, nach einem Beweis für P / poly NP / poly zu suchen . Lassen Sie uns jedoch den entfernten Motivationsabschnitt zusammenfassenvon der Frage wie "Der Ratschlag könnte ein formales axiomatisches System sein (das automatisch ein konsistentes, böses Grinsen garantiert), dessen Stärke mit der Länge der Eingabe schnell zunimmt, und NP ist äußerst gut darin, diesen Ratschlag auszunutzen." Wenn man nicht sehr vorsichtig ist, dass "Existenz einer Folge von Ratschlägen" nur "formale" Bedeutung in Bezug auf ein festes formales System hat, ist es wahrscheinlich, dass dieser Aufbau die Konstruktion von scheinbaren Paradoxien ermöglicht. Aber die Konstruktion solcher Paradoxien könnte trotzdem Spaß machen und vielleicht sogar Wege aufzeigen, wie man Unabhängigkeitsnachweise konstruiert (für ausreichend schwache formale Systeme).

Thomas Klimpel
quelle