Warum bevorzugen die meisten Menschen die Verwendung von Mehrfachreduzierungen, um die NP-Vollständigkeit zu definieren, anstatt zum Beispiel Turing-Reduzierungen?
cc.complexity-theory
np-hardness
reductions
Matthias
quelle
quelle
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.
quelle
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).
quelle
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 .
quelle
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)
quelle
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Σ1 Q
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?".
quelle
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.
quelle