Reduzierungen um ein Vielfaches im Vergleich zu Reduzierungen nach Turing, um NPC zu definieren

39

Warum bevorzugen die meisten Menschen die Verwendung von Mehrfachreduzierungen, um die NP-Vollständigkeit zu definieren, anstatt zum Beispiel Turing-Reduzierungen?

Matthias
quelle

Antworten:

32

Zwei Gründe:

(1) Nur eine Frage der Minimalität: NPC zu sein, ist eine formal stärkere Aussage, und wenn Sie die stärkere Aussage erhalten (wie Karp es tat und wie Sie es fast immer taten), warum sagen Sie es dann nicht?

(2) Wenn man von einer Reduzierung um ein Vielfaches spricht, entsteht eine feinere Hierarchie. Beispielsweise verschwindet die Unterscheidung NP gegen Co-NP unter Turing-Reduktionen.

Dies ähnelt im Geiste dem Grund, warum man häufig Logspace-Reduktionen anstelle von Polytime-Reduktionen verwendet.

Noam
quelle
16
Während (2) sicherlich wahr ist, kann ich (1) verwenden, um zu argumentieren, dass wir Eins-Eins-Reduktionen verwenden sollten. Da es sich bei den meisten von uns erstellten Reduktionen um Eins-zu-Eins-Reduktionen handelt, warum untersuchen wir diese nicht, wenn sie formal stärker sind und wir sie trotzdem die meiste Zeit erhalten? Ich denke, weil es einfacher ist, sich nicht die Mühe zu machen, die Injektivität zu beweisen, obwohl wir es normalerweise haben. In diesem Sinne sind viele Reduzierungen vielleicht eine Art "Goldlöckchen-Reduzierungen" - genau die richtige Kraft, genau die richtige Einfachheit des Beweises.
Joshua Grochow
21

Ich weiß nicht, ob es eine Präferenz gibt, aber es wird vermutet, dass es sich um unterschiedliche Vorstellungen handelt. Das heißt, Turing-Reduzierbarkeit wird als ein stärkerer Begriff vermutet. (Es gibt A und B, so dass A T-reduzierbar auf B ist, aber nicht Mo-reduzierbar auf B.) Ein Artikel, der dies diskutiert, ist dieser von Lutz und Mayordomo. Sie schlagen eine Verstärkung der Aussage P! = NP vor; ungefähr, dass NP eine nicht zu vernachlässigende Menge an EXPTIME enthält. Mit dieser Annahme können sie zeigen, dass die beiden Begriffe der Reduzierbarkeit unterschiedlich sind.

Aaron Sterling
quelle
17

Ich denke, der Grund, warum die Leute (zu Beginn) Reduzierungen mit vielen Einsern bevorzugen, ist pädagogisch - eine Reduzierung mit vielen Einsern von A nach B ist eigentlich eine Funktion für Saiten, während eine Reduzierung nach Turing die Einführung von Orakeln erfordert.

Beachten Sie, dass die Cook-Reduktion (Polynom-Time-Turing) und die Karp-Levin-Reduktion (Polynom-Time-Many-One) auf E unbedingt von Ko und Moore und separat von Watanabe (wie in der Veröffentlichung von Lutz und Mayordomo angegeben) verschieden sind in der Antwort von Aaron Sterling).

Joshua Grochow
quelle
7

Turing-Reduktionen sind in dieser Hinsicht mächtiger als Mapping-Reduktionen mit vielen Einsern: Mit Turing-Reduktionen können Sie eine Sprache ihrem Komplement zuordnen. Infolgedessen kann der Unterschied zwischen (zum Beispiel) NP und coNP in gewisser Weise verdeckt werden. In Cooks Originalarbeit untersuchte er diese Unterscheidung nicht (iirc Cook verwendete tatsächlich DNF-Formeln anstelle von CNF), aber es wurde wahrscheinlich sehr schnell klar, dass dies eine wichtige Trennung war, und viele Reduzierungen machten es einfacher, damit umzugehen .

Kurt
quelle
11
Stephen Cook wies während seiner Keynote auf der FLoC 2010 darauf hin, dass sein Aufsatz von 1971 tatsächlich den Nachweis erbringt, dass SAT für P ^ NP unter Turing-Reduktionen vollständig ist jemand, der weniger behauptet, als er bewiesen hat! Unter 4mhz.de/cook.html finden Sie eine neu gesetzte Version des Papiers. Auch der Satz "Wir konnten weder {Primzahlen} noch {isomorphe Graphenpaare} zu [der Liste der 4 NP-vollständigen Probleme] hinzufügen" bringt mich immer zum Lächeln!
András Salamon
5

Um hier von AS aus einem anderen Blickwinkel etwas abzuspringen / zu antworten, ist dies eine offene Frage (auch hier ) an den Grenzen von TCS, ob Cook-Reduzierungen ("Turing") von Karp-Levin-Reduzierungen ("Many-One") verschieden sind. möglicherweise äquivalent zu (Haupt-? Schlüssel-?) offenen Fragen der Trennung von Komplexitätsklassen. Hier ist ein neues Ergebnis in dieser Richtung

Trennung der Koch-Vollständigkeit von der Karp-Levin-Vollständigkeit unter einer Worst-Case-Härte-Hypothese / Debasis-Mandal, A. Pavan, Rajeswari Venugopalan (ECCC TR14-126)

Wir zeigen, dass es eine Sprache gibt, die für NP vollständig, für NP jedoch nicht für viele vollständig ist, unter einer Worst-Case- Härte-Hypothese.

vzn
quelle
4

Die Definitionen der effizienten Reduzierbarkeit sind zum Teil durch eine Analogie zur Rekursionstheorie motiviert. In der Rekursionstheorie sind die m-Reduktionen eng mit der arithmetischen Hierarchie verbunden. (m-Reduktionen erhalten den arithmetischen Grad). Arithmetische Klassifikationen sind nicht nur berechenbar. Zum Beispiel kann man sagen, dass wahre Aussagen in Robinsons nachweisbar sind . QΣ1Q

In der Komplexitätstheorie gibt es auch einen Begriff der "polynomiellen Hierarchie", obwohl im Gegensatz zur arithmetischen Hierarchie nur vermutet wird, dass sie existiert. Dies führt zu subtileren Klassifikationen als "Ist dieses Problem so schwer zu lösen wie NP?".

David Harris
quelle
3

Im Allgemeinen ist die Many-One-Reduktion (Karp) einfacher zu entwerfen, da es sich um eine eingeschränkte Form der Reduktion handelt, bei der ein Aufruf erfolgt, und die Hauptaufgabe darin besteht, die Eingabe in eine andere Codierung umzuwandeln. Die Reduzierung der Drehzahl kann eine komplexe Logik beinhalten. Die Existenz einer Menge, die für NP unter Turing-Reduktion, aber nicht unter Vielfachreduktion vollständig ist, impliziert, dass P! = NP ist.

Zum Beispiel ist die Unzufriedenheit für NP unter Cook-Reduktion vollständig, aber es ist nicht bekannt, dass sie für NP unter Karp-Reduktion vollständig ist. Wenn Sie also nachweisen, dass es keine Karp-Reduktion von SAT zu UNSAT gibt (äquivalent von UNSAT zu SAT), dann würden Sie nachweisen, dass NP! = CoNP und damit P! = NP.

Mohammad Al-Turkistany
quelle
Kannst du einen Verweis auf deinen letzten Satz geben oder ihn erklären?
Tayfun Pay
2
Ich erklärte meinen letzten Satz.
Mohammad Al-Turkistany