Sind

66

Derzeit ist die Lösung eines -kompletten Problems oder eines P S P A C E -kompletten Problems im allgemeinen Fall für große Eingaben nicht möglich. Beide sind jedoch in Exponentialzeit und Polynomraum lösbar.NPPSPEINCE

Macht es für uns einen Unterschied, ob ein Problem -complete oder P S P A C E -complete ist, da wir keine nicht deterministischen oder "glücklichen" Computer bauen können?NPPSPEINCE

Alex ten Brink
quelle

Antworten:

82

Dies ist eine sehr schöne Frage, über die ich viel nachgedacht habe: Beeinflusst die Tatsache, dass ein Problem -vollständig oder P S P A C E -vollständig ist, tatsächlich die Zeitkomplexität des Problems im schlimmsten Fall? NPPSPEINCEBeeinflusst eine solche Unterscheidung tatsächlich die Komplexität des Problems in der Praxis im "typischen Fall"?

Intuition besagt, dass das -Vollständigkeitsproblem schwieriger ist als das N P -Vollständigkeitsproblem, unabhängig davon, welches Komplexitätsmaß Sie verwenden. Aber die Situation ist subtil. Es könnte zum Beispiel sein, dass Q B F (Quantified Boolean Formulas, das kanonische P S P A C E -komplette Problem) genau dann in subexponentieller Zeit ist, wenn S A T (Satisfiability, the canonical N PPSPEINCENPQ.BFPSPEINCESEINTNP-vollständiges Problem) liegt in subexponentieller Zeit. (Eine Richtung ist offensichtlich; die andere Richtung wäre ein wichtiges Ergebnis!) Wenn dies zutrifft, ist es aus der Sicht von "Ich möchte dieses Problem nur lösen" vielleicht keine große Sache, ob das Problem -complete oder N P -complete: In beiden Fällen impliziert ein subexponentieller Algorithmus für den einen einen subexponentiellen Algorithmus für den anderen.PSPEINCENP

Lassen Sie mich ein Anwalt des Teufels sein und Ihnen ein Beispiel geben, in dem ein Problem "schwerer" als das andere ist, sich jedoch als "leichter zu handhaben" herausstellt als das andere.

Sei eine Boolesche Formel für n Variablen, wobei n gerade ist. Angenommen, Sie haben die Wahl zwischen zwei Formeln, über die Sie entscheiden möchten:F(X1,,Xn)nn

.Φ1=(X1)(X2)(Xn-1)(Xn)F(X1,,Xn)

Φ2=(X1)(X2)(Xn-1(Xn)F(X1,,Xn)

(Das heißt, in wechseln sich die Quantifizierer ab.)Φ2

Welches ist Ihrer Meinung nach leichter zu lösen? Formeln vom Typ oder Formeln vom Typ Φ 2 ?Φ1Φ2

Man würde denken, dass die offensichtliche Wahl , da es nur N P -vollständig ist, um sie zu entscheiden, wohingegen Φ 2 ein P S P A C E -vollständiges Problem ist. Tatsächlich ist Φ 2 nach unseren bekanntesten Algorithmen ein einfacheres Problem. Wir wissen nicht, wie man Φ 1 für general F in weniger als 2 n Schritten löst . (Wenn wir dies tun könnten, hätten wir neue Untergrenzen für die Formelgröße!) Aber Φ 2 kann leicht für jedes F in randomisiertem O gelöst werden (Φ1NPΦ2PSPEINCEΦ2Φ1F2nΦ2F Zeit, randomisierten SpielbaumSuche mit! Eine Referenz finden Sie in Kapitel 2, Abschnitt 2.1 in Motwani und Raghavan.O(2.793n)

Die Intuition ist, dass das Hinzufügen von universellen Quantifizierern das Problem tatsächlich einschränkt , wodurch es leichter zu lösen ist als schwieriger. Der Suchalgorithmus für Spielbäume basiert stark auf alternierenden Quantifizierern und kann keine willkürlichen Quantifizierungen verarbeiten. Dennoch bleibt der Punkt, dass Probleme unter einer Komplexitätsmaßnahme manchmal "einfacher" werden können, obwohl sie unter einer anderen Maßnahme "härter" aussehen können.

Ryan Williams
quelle
16
Schöne Antwort und eine interessante Einstellung.
Suresh Venkat
Mir fällt ein, dass das oben Genannte ein ziemlich gutes Beispiel für das ist, was wir unter "feinkörniger Komplexität" (ein Herbstprogramm 2015 am Simons Institute) verstehen. Eine der Schlüsselideen ist, dass die Komplexitätstheorie ganz anders aussehen kann, wenn man nicht für jedes Problem ein (möglicherweise bizarres) Rechenmodell zu finden versucht, für das dieses Problem "vollständig" ist, sondern sich einfach darauf konzentriert, die bestmögliche Laufzeit zu verstehen Exponent für das Problem.
Ryan Williams
37

Es ist wichtig, denn es geht um mehr als darum, ob wir Lösungen finden oder nicht. Interessant ist auch, ob wir Lösungen verifizieren können . Andere qualitative Unterscheidungen können zwischen der Schwierigkeit von Problemen getroffen werden, aber für NP gegenüber Klassen mit größerer Komplexität wäre dies diejenige, die ich als am wichtigsten erachten würde.

Für Entscheidungsprobleme - Probleme, für die jede Instanz eine " JA " - oder " NEIN " -Antwort hat - ist NP genau die Klasse von Problemen, für die wir einen angeblichen Beweis effizient überprüfen können, dass eine gegebene Instanz eine " JA " -Instanz ist, deterministisch, wenn wir werden mit einem vorgestellt. Wenn Sie beispielsweise eine zufriedenstellende Zuweisung von Variablen für eine Instanz von 3-SAT haben, können Sie mit dieser Zuweisung effizient nachweisen, dass die Instanz zufriedenstellend ist. Solch eine zufriedenstellende Aufgabe kann schwer zu finden sein, aber sobald Sie eine haben, können Sie anderen einfach beweisen, dass die Instanz zufriedenstellend ist, indem Sie die gefundene Lösung überprüfen lassen.

In ähnlicher Weise gibt es für coNP effizient überprüfbare Beweise für " NEIN " -Instanzen ; und für Probleme in NP  ∩  coNP , können Sie beides tun. Bei PSPACE- vollständigen Problemen gibt es jedoch keine derartigen Verfahren - es sei denn, Sie können einige recht spektakuläre Gleichheiten von Komplexitätsklassen nachweisen.

Niel de Beaudrap
quelle
Ich denke, dass die Frage nach "Optimierungs" -Versionen von NP-vollständigen und PSPACE-vollständigen Problemen ist. Gibt es zum Beispiel einen Unterschied (in Bezug auf die Komplexität) zwischen der Suche nach einer Lösung für SAT und für QBF? Und allgemeiner ausgedrückt: Gibt es eine Charakterisierung von Optimierungsproblemen, bei denen die Entscheidungsversion NP-vollständig oder PSPACE-vollständig ist?
Lamine
@Lamine: Ich erkenne nicht, welche Unterscheidung Sie in der Frage treffen (zumindest zwischen bloßer Entscheidung und vollständiger Optimierung). Vielleicht meinen Sie damit, dass der Fragesteller nur an der Frage interessiert ist, welche Ressourcen erforderlich sind, um diese Antwort zu finden, und dass er sich nicht für andere Schwierigkeitsgrade des Problems interessiert. In diesem Fall stimme ich zu, dass meine Antwort dies nicht beantwortet. In jedem Fall ist oben meine Antwort auf die Frage, wie sie steht.
Niel de Beaudrap
5
Sehr nette Antwort.
Dave Clarke
Die Fähigkeit, effizient zu verifizieren, hilft bei der Berechnung einer Lösung nicht (es sei denn, P = NP). NP und Co-NP ermöglichen es, das Problem durch Raten und Überprüfen anzugreifen. Dieser Ansatz ist einfach zu implementieren und möglicherweise sogar effizienter, hilft aber im schlimmsten Fall nicht.
András Salamon
@ András: Richtig - daher meine Betonung, dass das Finden von Lösungen nicht die einzige wichtige Sache im Vorwort zu meiner Antwort ist.
Niel de Beaudrap
36

Wir wissen nicht, wie wir aus (Worst-Case-) NP-vollständigen Problemen im Durchschnitt schwierige Probleme erstellen können, aber wir können dies für PSPACE tun (siehe Köbler & Schuler (1998) ), um Probleme zu erzeugen, die selbst über die gleichmäßige Verteilung nicht möglich sind wird bei den meisten Eingaben gelöst, es sei denn, PSPACE ist vollständig einfach zu berechnen.

Lance Fortnow
quelle
20

Aus praktischer Sicht ist es wichtig, sich daran zu erinnern, dass die NP-Vollständigkeit für viele Probleme in der Praxis kein Hindernis darstellt. Die beiden Tools von SAT-Solvern und CPLEX (für die ganzzahlige lineare Programmierung) sind leistungsstark und ausgereift genug, um häufig große Fälle von NP-vollständigen Problemen zu lösen, indem das Problem entweder als geeignetes ILP definiert oder auf SAT reduziert wird.

Ich kenne keine ähnlich ausgereiften Löser für Probleme in PSPACE.

Suresh Venkat
quelle
11
Es gibt einen jährlichen Wettbewerb zur Verbesserung der QBF-Löser . Ich habe sie nicht viel benutzt.
Radu GRIGore
7

Sie könnten es so sehen: Hat ein mathematisches Problem einen Beweis, der für Menschen lesbar ist, oder erfordert es von Natur aus einen "Computer-Beweis". Beispiele: Ist die Startposition der Dame ein Unentschieden? (Antwort: Ja.) Ist die Ausgangsposition von Schach ein Gewinn für Weiß? (Antwort: unbekannt, aber die meisten Absolventen halten es für unentschieden.)

Der Beweis, dass die Ausgangsposition der Kontrolleure ein Unentschieden ist, setzt voraus, dass man akzeptiert, dass der Computer wirklich viele Sonderfälle genau verifiziert hat. Wenn es jemals einen Beweis über Schach gibt, müssen menschliche Leser wahrscheinlich akzeptieren, dass ein Computer noch mehr Sonderfälle korrekt verifiziert hat. Und es kann durchaus sein, dass es keine kürzere Methode gibt, um diese Aussagen zu beweisen. Das sind Probleme in PSPACE. Wenn ein Problem in NP "nur" ist, dann könnte ein Mensch (intuitiv) den gesamten Beweis in seinem Kopf haben. Dieser Mensch muss natürlich ein sehr spezialisierter Mathematiker sein.

n1000000

Aaron Sterling
quelle
Könnte man auch argumentieren, dass bei coNP-vollständigen Problemen (manchmal) ein "Computer-Proof" erforderlich ist?
Philip White
@ Philip White: Ich denke nicht, dass es das gleiche ist. Sagen Sie, dass "Schach ein Unentschieden" in coNP ist. Um Nein zu sagen, muss ich nur eine einzige Forcierungslinie vorführen, die leicht überprüfbar ist. Wir gehen jedoch davon aus, dass es sehr schwer sein wird, zu beweisen, dass es sich tatsächlich um "Forcen" handelt, selbst wenn eine solche Linie existiert. Das Problem gibt also keine Garantie für Einfachheit, wenn es in eine bestimmte Richtung lösbar ist. "Schach ist ein Unentschieden" erfordert wahrscheinlich von sich aus, dass ein Computer beweist, ob es wahr oder falsch ist.
Aaron Sterling
5

Nach Sureshs Kommentar scheint es in der Praxis einen großen Unterschied zu geben. Es gibt Heuristiken, die es schaffen, die Struktur praktischer SAT-Instanzen auszunutzen und eine hervorragende Leistung zu erzielen (ich beziehe mich hier auf konfliktgetriebene Klausellernlöser). Dieselben Heuristiken führen bei QBF-Solvern nicht zu ähnlichen Leistungsverbesserungen.

Der Unterschied zwischen Beweis und Verifikation zeigt sich auch. Einige SAT-Löser (wie z. B. MiniSAT 1.14 und viele andere) erstellen Proofs. Das Erstellen von Proofs in aktuellen QBF-Solvern ist nicht trivial. (Die nächste Aussage stammt aus dem Hörensagen.) Es gibt große Fälle im QBF-Wettbewerb, in denen Löser offenbar unterschiedliche Ergebnisse erzielen. In Ermangelung von Proofgeneratoren wissen wir nicht, welches Ergebnis richtig ist.

Vijay D
quelle
0

Wenn Sie sich die praktische Leistung von SAT und Schach ansehen, dann gibt es einen Unterschied: NP-vollständige Probleme sind leichter zu lösen als PSPACE-vollständige Probleme. Heutzutage können SAT-Löser über tausend Variablen verarbeiten, aber die beste Schachengine kann in der gleichen Zeitspanne nur unter 20 Zügen rechnen.

Ich denke, das liegt an der Struktur der Probleme. Ja, wenn Sie nur Lösungen aufzählen, ist die SAT-Lösung sehr langsam. Da es jedoch keine quantifizierende Abwechslung gibt, entdecken die Leute Strukturen in der Formel und vermeiden daher viel Aufzählung. Ich denke, Ryan Williams hat diesen Punkt übersehen.

Mit Quantifier Alternation gibt es zwar intelligente Methoden zum Beschneiden, aber die Struktur ist nicht so reichhaltig wie die einer CNF-Formel.

Lassen Sie mich die Zukunft vorhersagen. Das SAT-Lösen schafft es zu P, indem die Formel untersucht und die Suche im Wesentlichen vermieden wird, während das Schachspiel es zu P schafft, indem die Suche im Spielbaum groß geschrieben wird.

Zirui Wang
quelle