Folgen von

34

Viele glauben, dass . Wir wissen jedoch nur, dass in der zweiten Ebene der Polynom-Hierarchie liegt, dh . Ein Schritt zum besteht darin, es zuerst auf die erste Ebene der zu bringen, dh .B P P B P P& Sigma; P 2& Pgr; P 2 B P P = P B P PN PBPP=PNPBPPBPPΣ2PΠ2PBPP=PBPPNP

Die Eindämmung würde bedeuten, dass der Nichtdeterminismus mindestens so mächtig ist wie die Zufälligkeit für die Polynomzeit.

Das bedeutet auch, dass wir die Antworten (in Polynomialzeit) effizient verifizieren können, wenn wir für ein Problem die Antworten mithilfe effizienter (Polynomialzeit) randomisierter Algorithmen finden können.

Gibt es bekannte interessante Konsequenzen für ?BPPNP

Gibt es Gründe zu der Annahme, dass der Nachweis von P derzeit unerreichbarBPPNP ist (z. B. Hindernisse oder andere Argumente)?

Kaveh
quelle
3
Ich glaube nicht, dass das bekannt ist coRPNP.

Antworten:

37

Zum einen würde der Beweis von leicht bedeuten, dass N E X P B P P , was bereits bedeutet, dass Ihr Beweis nicht relativieren kann.BPPNPNEXPBPP

coRPNTIME[2no(1)]NEXPP/poly

Ich persönlich weiß nicht, warum es "außer Reichweite" aussieht, aber es scheint schwer zu beweisen. Mit Sicherheit werden einige wirklich neue Tricks erforderlich sein, um dies zu beweisen.

Ryan Williams
quelle
12
Ein kleiner Nachtrag, falls es jemanden interessiert: Avi und ich dachten zwar nicht, dies in unserem Artikel zu tun, aber ich glaube, man kann ziemlich leicht durch Anpassen unserer Argumente (z. B. für NEXP vs. P / poly) nachweisen, dass ein BPP-Beweis vorliegt in NP müsste auch nicht-algebrierend sein.
Scott Aaronson
2
Scott: Ich habe keinen Zweifel, dass das auch wahr ist!
Ryan Williams
@RyanWilliams Gilt die Barriere für natürliche Beweise auch für BPP in NP? dies zu fragen, weil wie es möglich war, die Barriere zu überwinden (wenn überhaupt), um die Eindämmung in zu zeigen ? Σ2
T ....
2
Da natürliche Eigenschaften im Allgemeinen nur von Barrieren gegen ungleichmäßige (Schaltkreis-) Untergrenzen sprechen, weiß ich nicht, was sie darüber aussagen können, ob BPP in NP enthalten ist.
Ryan Williams
@ RyanWilliams ist "Permanent hat keine Poly-Size-Arithmetik-Schaltkreise" wie oder ist es schwächer? VNPVP
T ....