Kann man durch Turing-Reduktionen NP-Härte zeigen?

19

In der Arbeit Complexity of the Frobenius Problem von Ramírez-Alfonsín wurde mithilfe von Turing-Reduktionen nachgewiesen, dass ein Problem NP-vollständig ist. Ist das möglich? Wie genau? Ich dachte, dass dies nur durch eine polynomielle Zeitvielfachreduktion möglich wäre. Gibt es Referenzen dazu?

Gibt es zwei verschiedene Vorstellungen von NP-Härte, sogar NP-Vollständigkeit? Aber dann bin ich verwirrt, denn aus praktischer Sicht, wenn ich zeigen möchte, dass mein Problem NP-schwer ist, welches verwende ich?

Sie begannen die Beschreibung wie folgt:

Eine Polynomzeit Turing-Reduktion von einem Problem zu einem anderen Problem ist ein Algorithmus A, der unter Verwendung einer hypothetischen Subroutine A 'löst, um so zu lösen , dass A' ein Polynomzeitalgorithmus für wäre, dann wäre A eine Polynomzeit Algorithmus für . Wir sagen, dass auf reduziert werden kann .P 2 P 1 P 2 P 2 P 1 P 1 P 2P1P2P1P2P2P1P1P2

Ein Problem heißt (Turing) NP-schwer, wenn ein NP-vollständiges Entscheidungsproblem so dass Turing auf reduziert werden kann .P 2 P 2 P 1P1P2P2P1

Und dann verwenden sie eine solche Turing-Reduktion aus einem NP-vollständigen Problem, um die NP-Vollständigkeit eines anderen Problems aufzuzeigen.

user2145167
quelle

Antworten:

17

Es gibt (mindestens) zwei verschiedene Begriffe der NP-Härte. Der übliche Begriff, der Karp-Reduktionen verwendet, besagt, dass eine Sprache NP-hart ist, wenn jede Sprache in NP Karp auf L reduziert wird . Wenn wir Karp-Reduzierungen in Cook-Reduzierungen ändern, erhalten wir einen anderen Begriff. Jede Sprache, die Karp-NP-hart ist, ist auch Cook-NP-hart, aber das Gegenteil ist wahrscheinlich falsch. Nehmen wir an, dass NP verschieden von coNP ist, und nehmen Sie Ihre Lieblings - NP-vollständige Sprache L . Dann ist das Komplement von L Cook-NP-hart, aber nicht Karp-NP-hart.LLLL

Der Grund , dass ist Koch-NP-schwer ist folgende: jede Sprache nimmt M in NP. Da L NP-hart ist, gibt es eine polytime Funktion f derart , daß x M iff f ( x ) L iff f ( x ) ¯ L . Ein Koch Reduktion von M zu ··· L nimmt x berechnet f ( x ) , überprüft , ob f ( x ) ¯L¯MLfxMf(x)Lf(x)L¯ML¯xf(x) und gibt das Gegenteil aus.f(x)L¯

Der Grund , dass nicht NP-hard ist (unter der Annahme NP unterscheidet sich von coNP) ist die folgende. Angenommen ·········· L waren NP-hart. Dann für jede Sprache M in coNP, gibt es eine Reduktion polytime f , so daß x ¯ M iff f ( x ) ¯ L , oder mit anderen Worten, x M iff f ( x ) L . Da L in NP ist, zeigt dies, dass M in NP ist und somit coNP L¯L¯MfxM¯f(x)L¯xMf(x)LLMNP. Dies impliziert sofort, dass NP coNP und somit NP = coNP ist.

Wenn eine Cook-NP-harte Sprache in P ist, dann ist P = NP: Verwenden Sie für jede Sprache M in NP die Cook-Reduktion auf L , um einen Polyzeitalgorithmus für M zu erhalten . In diesem Sinne sind Cook-NP-vollständige Sprachen auch "am härtesten in NP". Auf der anderen Seite ist es einfach , dass Cook-NP-hard = Koch-coNP-schwer zu sehen: eine Cook - Reduktion für L kann auf eine Cook - Reduktion umgewandelt werden ˘ L . Daher verlieren wir etwas an Präzision, wenn wir Cook-Reduzierungen verwenden.LMLMLL¯

Es gibt wahrscheinlich andere Mängel bei der Verwendung von Cook-Reduzierungen, aber das überlasse ich anderen Antwortenden.

Yuval Filmus
quelle
Ich habe das alles noch nicht ganz verstanden, muss ich sagen. Aber ich habe eine andere Frage, vielleicht können Sie diese beantworten (da es nicht so viele andere Antworten gibt): Was ist, wenn ich ein Turing-Rot habe? von NP-komplettes Problem A zu etwas Problem B und einem Karp-Rot. von Problem B zu Problem C. Stellt dies die NP-Vollständigkeit von Problem C fest (Mitgliedschaft ist kein Problem)? Und generell kann ich das Problem B NP-hart oder eher (Turing) NP-hart nennen? Vielen Dank!
user2145167
3
Zwei Karp-Reduktionen ergeben eine Karp-Reduktion und zwei Cook-Reduktionen ergeben eine Cook-Reduktion. Da eine Karp-Reduktion auch eine Cook-Reduktion ist, erhalten Sie eine Cook-Reduktion, wenn Sie eine Karp-Reduktion und eine Cook-Reduktion zusammenstellen. Im Allgemeinen erhalten Sie jedoch keine Karp-Ermäßigung.
Yuval Filmus
@YuvalFilmus, könnten Sie bitte erläutern, was Sie mit iff f ( x ) L iff f ( x ) ¯ ¯ L meinen wollten ? xMf(x)Lf(x)L¯
Omar Shehab
Eine Karp-Reduktion von nach L ist eine Funktion f (in diesem Fall polytime), so dass x M iff f ( x ) L ist . Für jeden f , x immer das gilt f ( x ) L iff f ( x ) ¯ L , wobei ¯ L das Komplement von ist L (in Bezug auf den Bereich von f ). MLfxMf(x)L f,xf(x)Lf(x)L¯L¯Lf
Yuval Filmus
6

Das ist gut. Eine Polynom-Zeit-Turing-Reduktion ist eine Cook-Reduktion (wie im Cook-Levin-Theorem), und die Reduktion eines NP-vollständigen Problems auf das neue Problem ergibt eine NP-Härte (wie eine Polynom-Zeit-Viel-Eins-Reduktion, AKA-Karp-Reduktion). Tatsächlich sind Karp-Reduzierungen ohnehin nur auf Turing-Reduzierungen beschränkt.

Wo sie sich (in Bezug auf diese Frage) unterscheiden, zeigt sich die Mitgliedschaft. Eine Karp-Reduktion von einem Problem zu einem Problem in NP zeigt, dass sich das erste in NP befindet. Eine Cook-Reduzierung in die gleiche Richtung tut dies nicht.

Luke Mathieson
quelle
Vielen Dank. Mir war nicht einmal bewusst, dass man Mitgliedschaft durch explizite Verwendung einer Karp-Reduktion zeigt. Aber es macht Sinn. Aber man kann die NP-Mitgliedschaft zeigen, indem man eine Turing-Reduktion in beide Richtungen verwendet, oder?
user2145167
1
@ user2145167 nein, Yuvals Antwort gibt hier die ganze Geschichte wieder, aber kurz gesagt, die Cook-Reduktionen sind schwächer, lassen Sie also mehr zu - Sie können z wahr für Karp Reduktionen.
Luke Mathieson