Folgen von und ?

12

Wir wissen, dass wenn ist, der gesamte PH zusammenbricht. Was ist, wenn die Polynomhierarchie teilweise zusammenbricht? (Oder wie kann man verstehen, dass PH über einem bestimmten Punkt und nicht unter einem bestimmten Punkt zusammenbrechen kann?)P=NP

Mit kürzeren Worten, was wären die Konsequenzen von und ?P N P.NP=coNPPNP

Xavier Labouze
quelle
3
In diesem Fall kollabiert PH immer noch (auf die 1. statt auf die 0. Ebene).
Huck Bennett
Der erste Satz scheint auszudrücken, dass "wir in Schwierigkeiten sind, wenn P = NP nicht ist, weil die Hierarchie zusammenbricht", was nicht korrekt ist (abgesehen von der möglicherweise kontroversen Frage, ob P = NP eine problematische Situation ist oder nicht).
Kaveh
2
@Huck Ich denke, OP versucht möglicherweise zu fragen, was die Konsequenzen eines Zusammenbruchs von PH auf die 1. Ebene sind. Welche coolen Probleme könnten wir dann lösen?
Artem Kaznatcheev
@ Xavier: Warum sagst du "... und wir sind in Schwierigkeiten" . P = NP und der daraus resultierende PH-Zusammenbruch wären einfach fantastisch ;-)
Giorgio Camerani
@ ArtemKaznatcheev: tks zu Ihrem Verständnis Kommentar
Xavier Labouze

Antworten:

17

Für mich ist eine der grundlegendsten und überraschendsten Konsequenzen von das Vorhandensein kurzer Beweise für eine ganze Reihe von Problemen, bei denen es sehr schwierig ist zu erkennen, warum sie kurze Beweise haben sollten. (Dies ist eine Art Rückschritt von "Welche anderen Auswirkungen auf die Komplexität hat dieser Zusammenbruch?" Zu "Was sind die grundlegenden, bodenständigen Gründe, warum dieser Zusammenbruch überraschend wäre?")NP=coNP

Wenn beispielsweise ist, gibt es für jeden Graphen, der nicht Hamilton ist, einen kurzen Beweis für diese Tatsache. Ähnliches gilt für Diagramme, die nicht dreifarbig sind. Ähnliches gilt für Paare von Graphen, die nicht isomorph sind. Ähnliches gilt für jede Satztautologie .NP=coNP

In einer Welt, in der , besteht die Schwierigkeit beim Nachweis von nicht darin, dass einige kurze Tautologien lange Beweise haben - denn in einer solchen Welt hat jede Tautologie ein Polynom Kurzer Beweis - sondern dass es einen anderen Grund gibt, warum wir diese Beweise nicht effizient finden können.PNP=coNP

Joshua Grochow
quelle
Ich mag diese Antwort! +1
Tayfun Pay
Tks für Ihre Antwort, die unterstrichene Konsequenz ist ziemlich überraschend. Ich frage mich, aus welchem anderen Grund diese Beweise nicht effizient gefunden werden können. Irgendeine Idee ?
Xavier Labouze
12

Wenn wir auch annehmen , würde die Hypothese auch den Zusammenbruch randomisierter Klassen verursachen:NP=RP . Obwohl vermutet wird, dass diese alle bedingungslos in P zusammenbrechen , ist noch offen, ob dies tatsächlich geschieht. In jedem Fallscheint N P = c o N P an sich nicht zu implizieren, dass diese randomisierten Klassen zusammenbrechen.ZPP=RP=CoRP=BPPPNP=coNP

Wenn dies nicht der Fall ist, dh wir haben zumindest , dann hätte dies zusammen mit der Hypothese N P = c o N P eine weitere wichtige Konsequenz:BPPPNP=coNP . Dies ergibtaus einer Folge von Babai, Fortnow, Nisan und Wigderson, die besagtdasswenn alle unären (tally) Sprachen in P H fallen in P , dann B P P = P . Wenn also B P PP ist , können sie nicht alle in P fallen , da dieAnnahme N P = c o N P P H = N P impliziert. Daher muss es in N P - P eine Zählsprache gebenENEPHPBPP=PBPPPPNP=coNPPH=NPNPP. Schließlich ist bekannt, dass das Vorhandensein einer Tally-Sprache in EN E impliziert .NPPENE

Die obige Überlegung zeigt den interessanten Effekt, dass die Hypothese , obwohl sie ein Kollaps ist, tatsächlich die Trennkraft von B P PP verstärkt , da nicht bekannt ist, dass letztere allein EN E impliziert . Diese "Anomalie" scheint die Vermutung B P P = P zu stützen .NP=coNPBPPPENEBPP=P

Andras Farago
quelle
1
Vielleicht bin ich hier langsam, aber wie bedeutet NP = coNP ZPP = RP = coRP = BPP?
Joshua Grochow
@ JoshuaGrochow Ich stecke auch dabei fest.
Tayfun Pay
Danke, ich habe tatsächlich eine Bedingung verpasst. Ich habe die Antwort korrigiert.
Andras Farago
@AndrasFarago okay! +1 :)
Tayfun Pay
@AndrasFarago Tks für Ihre Antwort!
Xavier Labouze
7

#P

ValiantsDefinition:_C#C=AC(#P)A(#PA)A

#NP=#CoNP

TodasDefinition:_C#.CfCRpxf(x)=||{y|p(|x|)=|y|R(x,y)}||

#.NP=#.CoNPNP=CoNP

PNPFP#P

Tayfun Pay
quelle
Es ist die Zählversion von NP.
Tayfun Pay
Worauf bezieht sich der Zeitraum in "# .NP"?
Timothy Sun
4
Es gibt zwei Arten, wenn Zählhierarchien definiert sind. Einer von Valiant aus dem Jahr 1979 und er verwendet die Notation #P, # NP, # Co-NP ... Wobei # NP = Co-NP. Andererseits hat Toda eine andere Hierarchie definiert. Und die Notation dafür verwendet Punkte. Und # .NP! = #. Co-NP, es sei denn, NP = Co-NP
Tayfun Pay
2

Ker-i Ko hat gezeigt, dass es ein Orakel gibt, das PH auf der k-ten Ebene zusammenbrechen lässt. Siehe "Ker-I Ko: Relativierte Polynomzeithierarchien mit genau K-Ebenen. SIAM J. Comput. 18 (2): 392-408 (1989)".

Bin Fu
quelle
Können Sie uns mit dem Papier verknüpfen?
Tayfun Pay
@ BinFu Tks - Ich dachte, dass PH auf die erste Ebene zusammenbricht ...
Xavier Labouze
1
Für den Fall k = 1 ist dies der Fall. Die Polynomzeit kollabiert unter der Bedingung NP = coNP zu NP. Die Existenz des Orakels für die k-te Ebene in Ko's Arbeit bedeutet die Barriere jeder relativierten Methode zur Behandlung des PH-Kollaps-Problems.
Bin Fu
1
@ BinFu: Ihre Bemerkungen beschreiben keine Konsequenzen von PNP = coNP . Die Frage war nicht , wie zu zeigen , einen Zusammenbruch der ersten Ebene oder über Ergebnisse , die auch einen Zusammenbruch auf der ersten Ebene beschreiben, aber was als logische Folge eines Zusammenbruchs auf der ersten Ebene bekannt ist. Ich verstehe nicht, wie sich Ihre Antwort darauf auswirkt.
Niel de Beaudrap
1
Jede erfüllbare Boolesche Formel hat einen Polynom-Zeit- und Längenbeweis, der die Wahrheitszuweisungen darstellt, um die Formel wahr zu machen. Die Bedingung NP = coNP bewirkt, dass jede unbefriedigende boolesche Formel einen Polynomzeit- und Längennachweis hat. Wenn P nicht gleich NP ist und NP = coNP, gibt es keinen Polynomzeitalgorithmus, um den Polynomlängenbeweis für eine Boolesche Formel für ihre Erfüllbarkeit oder Unerfüllbarkeit zu finden. In ähnlicher Weise werden wir ähnliche Schlussfolgerungen für alle Probleme in NP ziehen.
Bin Fu