Folgen vollständiger Probleme für NP überschneiden sich mit coNP

24

Was sind die Konsequenzen von vollständigen Problemen in ?NPcoNP

Marcos Villagra
quelle
Siehe auch mathoverflow.net/questions/34889/…
Jukka Suomela
Ich kenne diesen Link. Meine Frage betrifft die Konsequenzen. Wenn zum Beispiel die Sprache L für vollständig ist, PH auf die Ebene oder so ähnlich. NPcoNPi
Marcos Villagra
Eigentlich habe ich dieselbe Frage gestellt wie einen Kommentar in diesem Link, aber ich wollte es zu einer echten Frage machen.
Marcos Villagra
2
Ja, ich weiß, dass Sie es wissen, aber die Mathoverflow-Seite bietet nützliche Hintergrundinformationen für andere.
Jukka Suomela

Antworten:

18

Dies ist ein (weit) offenes Problem; Wir wissen so gut wie nichts. Insbesondere wegen der Tücken in beweisen NPcoNP -komplette Probleme, müssen wir sehr unterschiedliche Beweistechniken , als derzeit vorhanden sind . Als solches sollte eine Diskussion der Konsequenzen vernünftigerweise eine Tangente beinhalten: "Was würde es bedeuten, solch mächtige, neue Beweisverfahren zu haben?"

Für eine relativ aktuelle Diskussion des Themas gibt es die 26. NP-Completeness-Kolumne von David Johnson in der ACM Transactions on Algorithms from 2007 ( PDF ). Erlauben Sie mir , einige zu paraphrasieren , was David sagt in Bezug auf die Frage des Nachweises NPcoNP -komplette Probleme Existenz und fügen Sie meine Gedanken:

Derzeit haben wir nur "schwache" natürliche Kandidaten für eine Mitgliedschaft in NPcoNPP in dem Sinne, dass der stärkste Beweis für ihre Mitgliedschaft darin besteht, dass wir noch keinen polynomiellen Zeitalgorithmus für sie gefunden haben. Er listet einige Kandidaten auf: SMALL FACTOR, SIMPLE STOCHASTIC GAME und MEAN PAYOFF GAME. Einige der extra „Seltsamkeit“ diese Probleme kommen aus den besten Heuristik Laufzeiten für die Lösung von ihnen, zum Beispiel kleiner Faktor, auch bekannt als ganzzahliger Faktors k , hat eine randomisierte Zeitkomplexität von poly(n)2klog(k) . (Wenn inNPcoNPPvollständige Probleme existieren, ist danneine solche subexponentielle(weder rein exponentielle noch ganz polynomielle)Laufzeit der Klasse endemisch?)

So gesagt, wollten wir etwas beweisen , wie: Problem A nur in ist P genau dann , wenn NPcoNP=P , dh ein Vollständigkeits Ergebnis wie Cooks Satz für 3SAT und NP . Für NP solche Beweise allgemein eine Polynomzeitverkürzung (und legen Ihre bevorzugten zusätzlichen Beschränkungen fest, z. B. Kochverkürzungen, Karp-Verkürzungen). Infolgedessen muss es unter Techniken zur Verringerung der Polynomzeit eine polynomzeiterkennbare Darstellung der Klasse geben. Für NP können wir nichtdeterministische Turing-Maschinen verwenden, die innerhalb eines Polynoms p anhaltenp(|x|) , Anzahl der Schritte. Wie David weist darauf hin, haben wir ähnliche Darstellungen für andere Klassen wie (wo der Status mehr klar ist)PSPACE und#P .

Die Schwierigkeit jedoch mit einer ähnlichen Darstellung für die Bereitstellung von NPcoNP ist , dass die „natürliche“ Analog ermöglicht uns einzubetten das Halteproblem in der Darstellung und ist somit unentscheidbar . Betrachten wir also den folgenden Versuch, NPcoNP mit zwei nicht deterministischen Turing-Maschinen darzustellen , die angeblich komplementäre Sprachen erkennen:

Frage: Gibt es eine Turing - Maschine M halt auf Eingabe x0,1n ?

Konstruieren Sie zwei Linearzeit-Turingmaschinen M1 und M2 wie folgt. Bei der Eingabe y , M1 liest die Eingabe und immer akzeptiert. M2 lehnt immer ab, es sei denn |y||x|und M akzeptiert x in Schritten |y|.

Daher akzeptieren M1 und M2 komplementäre Sprachen, wenn M bei Eingabe x nicht anhält . Daher ist es widersprüchlich, zu entscheiden, ob zwei Polynom-Zeit-Turing-Maschinen komplementäre Sprachen akzeptieren.

Die "natürliche" Darstellung von NPcoNP Problemen ist also nicht polynomialzeitlich erkennbar. Es bleibt die Frage: Wie stellen Sie NPcoNP Probleme , so dass sie Polynom-Zeit erkennbar sind?

Es wurden keine wesentlichen Arbeiten zu diesem Thema durchgeführt, aber die erfolgreiche Lösung ist erforderlich, um die Vollständigkeit in NPcoNP zu beweisen . Daher behaupte ich, dass die Existenz einer Beweismethode, die die Vollständigkeit von NPcoNP auflösen kann, die größere Geschichte sein wird - nicht die "automatischen" Ergebnisse von NPcoNP vollständigen Problemen ( zB Komplexitätsklassen, vielleicht, kollabiert) , dass wir bereits kennen (oder besser gesagt, wird sich bewusst sein , hypothetisch in der Zukunft).

Daniel Apon
quelle
1
danke für das pdf. Ich habe es noch nicht gelesen, werde es aber tun. Es gibt diese Arbeit: "Über Gesamtfunktionen, Existenzsätze und Rechenkomplexität". Nimrod Megiddo und Christos Papadimitriou. Theoretical Computer Science 81, 1991. Es geht nicht um , sondern um die zugehörige Funktionsklasse TFNP, dh T F N P = F ( N P c o N P ) . Es gibt den folgenden Satz: "Es gibt ein FNP-vollständiges Problem in TFNP, wenn NP = coNP". Gegeben, dass Such- und Entscheidungsprobleme polynomial zusammenhängen, erstreckt sich dieser Satz auch auf N PNPcoNPTFNP=F(NPcoNP) ? Wenn ja, wird dies einen großen Zusammenbruch der PH bedeuten. Ist das richtig? NPcoNP
Marcos Villagra
Dies wird nicht direkt übersetzt (wie ich glaube, dass Sie dies implizieren). Beachten Sie, dass sich der Satz nicht nur auf JEDES vollständige Problem bezieht, sondern auf ein FNP-vollständiges Problem. Dies entspricht der Aussage "Es gibt ein NP-vollständiges Problem in NP \ cap coNP, wenn NP = coNP." Soweit mir bekannt ist, ist es denkbar, dass NP \ cap coNP vollständige Probleme haben, die sich von NP-vollständigen Problemen unterscheiden, ohne dass PH zusammenbricht . (Link ist zum Spaß.;))
Daniel Apon
Anmerkung: Es wird immer noch als unwahrscheinlich angesehen, dass die oben beschriebene Situation aus den gleichen Gründen wie in der Antwort der Fall ist.
Daniel Apon