Reduktionsarten und zugehörige Definitionen der Härte

15

Sei A nach B, das heißt reduzierbar sein . Daher Akzeptieren die Turing Maschine A hat Zugang zu einer Oracle für B . Lassen Sie die Turing Maschine Annahme A seine M A und die Oracle für B sein O B . Die Arten von Ermäßigungen:ABABAMABOB

  • Turing - Reduktion: können mehrere Abfragen machen O B .MAOB

  • Karp-Reduktion: Auch als "Polynomzeit-Turing-Reduktion" bezeichnet: Die Eingabe für muss in Polyzeit erstellt werden. Darüber hinaus ist die Anzahl der Anfragen an O B muss durch ein Polynom begrenzt werden. In diesem Fall: P A = P B .OBOBPA=PB

  • Many-One-Turing-Reduktion: kann im letzten Schritt nur eine Anfrage an O B stellen . Daher kann die Orakelantwort nicht geändert werden. Allerdings ist die Zeit konstruiert , um die Eingabe zu genommen O B braucht nicht durch ein Polynom begrenzt werden. Äquivalent: ( m steht für eine Reduzierung um ein Vielfaches)MAOBOBm

    , wenn eine berechenbare Funktion f : Σ *Σ * , so dass F ( x ) BAmBf:ΣΣ .f(x)BxA

  • Kochreduktion: Auch als "Polynomzeit-Vielfachreduktion" bezeichnet: Eine Vielfachreduktion, bei der die Zeit, die zum Erstellen einer Eingabe für , durch ein Polynom begrenzt werden muss. Äquivalent: ( p m bedeutet eine Reduktion um ein Vielfaches)OBmp

    , wenn einerpoly-timeberechenbare Funktion f : Σ *Σ * , so dass F ( x ) BAmpBf:ΣΣ .f(x)BxA

  • Sparsame Reduktion: Auch als "Polynom-Zeit-Eins-Eins-Reduktion" bezeichnet: Eine Cook-Reduktion, bei der jede Instanz von einer eindeutigen Instanz von B zugeordnet wird . Äquivalent: ( p 1 bedeutet sparsame Reduktion)AB1p

    , wenn einerpoly-Zeitberechenbar Bijektion f : Σ *Σ * , so dass F ( x ) BA1pBf:ΣΣ .f(x)BxA

    Diese Reduzierungen erhalten die Anzahl der Lösungen. Daher .#MA=#OB

Wir können weitere Arten von Kürzungen definieren, indem wir die Anzahl der Orakelabfragen begrenzen. Wenn Sie diese jedoch weglassen, kann mir jemand freundlich mitteilen, ob ich die Nomenklatur für die verschiedenen Arten von Kürzungen korrekt erhalten habe. Sind NP-vollständige Probleme in Bezug auf Kochreduktion oder sparsame Reduktion definiert? Kann jemand freundlicherweise ein Beispiel für ein Problem geben, das unter Cook NP-vollständig und nicht unter sparsamer Reduktion ist.

Wenn ich mich nicht irre, ist die Klasse # P-Complete in Bezug auf Karp-Reduktionen definiert.

Pavithran Iyer
quelle

Antworten:

7

Ihre Definition von sparsamen Kürzungen ist falsch. Sie verwechseln es mit polynomialen Eins-Eins-Reduktionen, was ein Sonderfall von Karp-Reduktionen ist. Sie bewahren nicht die Anzahl der "Lösungen". In dieser Antwort finden Sie weitere Informationen zu Ermäßigungen in Bezug auf die Anzahl der Zertifikate.

Der Rest scheint in Ordnung zu sein, obwohl es normalerweise besser ist, sie in einem zweidimensionalen Diagramm anzuzeigen:

  • die Komplexität der Reduktion: berechenbare, polynomiale Zeit, logarithmischer Raum usw.
  • Art des Zugangs: Turing, Many-One, One-One, etc.

Sind NP-vollständige Probleme in Bezug auf Kochreduktion oder sparsame Reduktion definiert?

NP

Kann jemand freundlicherweise ein Beispiel für ein Problem geben, das unter Cook NP-vollständig und nicht unter sparsamer Reduktion ist.

NPNP

Die Klasse # P-Complete ist in Bezug auf Karp-Reduktionen definiert

#P

Kaveh
quelle
Entschuldigung, anscheinend habe ich die Terminologie "Karp-Reduktion" und "Cook-Reduktion" vertauscht. Wenn ich es vertausche, entspricht es Ihren Antworten. Vielen Dank. Sagen Sie in Bezug auf sparsame Kürzungen, dass die Anzahl der "Lösungen" nicht erhalten bleibt? Wenn ja, sehe ich in Satz 17.10 von Arora & Barak (Seite 299), dass sparsame Reduktionen tatsächlich die Anzahl der Lösungen bewahren. Eine weitere Referenz: ( cse.cuhk.edu.hk/~andrejb/csc5170/notes/10L10.pdf )
Pavithran Iyer
Hier heißt es eine sparsame Reduktion von L auf SAT, ordnet jede Instanz x von L einer eindeutigen Instanz von SAT zu ( dh die Reduktionskarte ist eins zu eins): [ cse.cuhk.edu.hk/~andrejb/csc5170/notes /10L10.pdf] . Ist es nicht richtig anzunehmen, dass die Karte eins zu eins ist, wenn die Anzahl der Lösungen durch eine Reduzierung erhalten bleibt?
Pavithran Iyer
@Pavithran, was Sie in Ihrer Frage geschrieben haben, war nicht die Definition von sparsamen Kürzungen. Die Antwort finden Sie in der Übung 2.13 in ihrem Buch.
Kaveh
0

OB

Björn Lindqvist
quelle
Insbesondere wurden die Definitionen von Cook- und Karp-Reduktionen geändert.
David Richerby