Ist die Karp-Reduktion identisch mit der Levin-Reduktion?

12

Definition: Karp-Reduktion

Eine Sprache AA ist Karp reduzierbar auf eine Sprache BB , wenn es eine Polynom-berechenbare Funktion ist f : { 0 , 1 } *{ 0 , 1 } *f:{0,1}{0,1} so dass für jeden xx , x AxA , wenn und nur wenn f ( x ) Bf(x)B .

Definition: Levinreduktion

Ein Suchproblem V AVA ist Levin auf ein Suchproblem reduzierbaren V BVB , wenn es Polynomzeit Funktion ist ff die Karp reduziert L ( V A )L(VA) bis L ( V B )L(VB) , und es gibt Polynom-berechenbare Funktionen gg und hh , so dass

  1. X , y V AF ( x ) , g ( x , y ) V Bx,yVAf(x),g(x,y)VB ,

  2. f ( x ) , z V BX , h ( x , z ) V Af(x),zVBx,h(x,z)VA

Sind diese Ermäßigungen gleichwertig?


Ich denke, die beiden Definitionen sind gleichwertig. Für zwei beliebige N P Sprachen A und B , wenn A ist Karp reduzierbar auf B , dann A ist Levin reduzierbar auf B .NPABABAB

Hier ist mein Beweis:

Lassen Sie x und ¯ x beliebige Instanzen seine A , während x ' , dass der sein B . Angenommen , V A und V B sind Verifizierer von A und B . Lassen y und ¯ y beliebige Zertifikate werden x und ¯ x nach V Axx¯¯¯AxBVAVBAByy¯¯¯xx¯¯¯VA . Lassen z sein , daß von x ' nach V B .zxVB

Konstruiere neue Verifizierer V ' A und V ' BVAVB mit neuen Zertifikaten y ' und z ' :yz

V ' A (x,y'):VA(x,y):

  1. y ' = 0 , ¯ x , ¯ y : Wenn f ( x ) f ( ¯ x ) , abweisen. Andernfalls Ausgang V A ( ¯y=0,x¯¯¯,y¯¯¯f(x)f(x¯¯¯) x , ¯ y ).VA(x¯¯¯,y¯¯¯)
  2. y ' = 1 , z : Ausgang V B ( f ( x ) , z ) .y=1,zVB(f(x),z)

V ' B ( x ' , z ' ) :VB(x,z):

  1. z ' = 0 , z : Ausgang V B ( x ' , z ) .z=0,zVB(x,z)

  2. z ' = 1 , x , y : Wenn x 'f ( x ) , abweisen. Andernfalls Ausgang V A ( x , y ) .z=1,x,yxf(x)VA(x,y)

Die zur Polynomzeit berechenbaren Funktionen g und h sind wie folgt definiert:gh

g ( x , y ' )g(x,y)

  1. y ' = 0 , ¯ x , ¯ y : Ausgabe1 , ¯ xy=0,x¯¯¯,y¯¯¯ , ¯ y .1,x¯¯¯,y¯¯¯

  2. y ' = 1 , z y=1,z : Ausgabe 0 , z .0,z

h ( x ' , z ' )h(x,z)

  1. z ' = 0 , z z=0,z : Ausgabe 1 , z .1,z

  2. z ' = 1 , x , y z=1,x,y : Ausgabe 0 , x , y .0,x,y

Lassen Y x die Menge aller Zertifikate von x nach V A und Z x ' sein , die Menge aller Zertifikate von x ' nach V B . Dann ist die Menge aller Zertifikate von x nach V ' A ist 0 ¯ x Y ¯ x + 1 Z f ( x ) derart , dass f ( x ) = f ( ¯ x )YxxVAZxxVBxVA0x¯¯¯Yx¯¯¯+1Zf(x)f(x)=f(x¯¯¯)Und die Menge aller Zertifikate von x ' gemäß = f ( ¯ x ) .xV ' B ist 0 Z x ' + 1 ¯ x Y ¯ x , so daß x 'VB0Zx+1x¯¯¯Yx¯¯¯x=f(x¯¯¯)

(Dies ergibt sich aus der akzeptierenden Sprache von V A undVA V ' B ab .)VB

Nun lass x = f ( x ) , der Rest ist leicht zu überprüfen.x=f(x)

cc
quelle
Bevor Sie Ihren Anspruch beweisen, sollten Sie definieren, was es bedeutet, wenn eine Sprache Levin ist, das auf eine andere reduziert werden kann.
Tsuyoshi Ito

Antworten:

14

Nein. Beachten Sie zunächst, dass die Levinreduktion nur für Klassen sinnvoll ist, deren Zertifikat eine Bedeutung hat, z. B. N P, während die Karpreduktion allgemein ist. Das Wort "Zertifikat" für ein Problem ist nur dann sinnvoll, wenn ein Verifizierer behoben ist. Levins Reduktion setzt voraus, dass die Verifizierer feststehen. Sie können die Verifizierer nicht ändern. (Im Folgenden gehe ich davon aus, dass Zertifikatsüberprüfer gemäß der Definition der Levinreduktion festgelegt sind.)NP

Zweitens bedeutet Levin-Reduktion, dass man das Zertifikat für das eine aus dem Zertifikat für das andere herausfinden kann. Es ist wahr, dass sich die bekannten Karp-Reduktionen zwischen natürlichen Problemen als Levin-Reduktion herausstellen, aber dies muss im Allgemeinen nicht wahr sein.

Wenn wir die Fälle von Problem A auf Problem B reduzieren könnenAB heißt das nicht, dass wir die Möglichkeit haben, ein Zertifikat für das eine aus einem Zertifikat für das andere zu berechnen.

Damit dies zutrifft, benötigen wir die Tatsache, dass ein Zertifikatssuchproblem, das dem Entscheidungsproblem entspricht, eine Polynomzeit ist, die auf das Entscheidungsproblem reduziert werden kann. Dies gilt für N P - c o m p l e t e Probleme, es ist jedoch nicht bekannt, dass dies im Allgemeinen auch für N P Probleme gilt.NP-completeNP

Kaveh
quelle
Ich stimme Ihrem ersten Punkt zu, dass die Karp-Reduktion allgemeiner ist als die Karp-Reduktion. Demnach denke ich, mein Problem sollte modifiziert werden als "Sei L 1 und L 2 zwei Sprachen in N P. Wenn L 1 Karp ist, reduzierbar auf L"L1L2NPL1 2, dann ist L 1 Levin auf L 2 reduzierbar." Allerdings stimme ich Ihren anderen Kommentaren nicht zu. L2L1L2
cc
In meinem Beweis seien L 1 und L 2 zunächst willkürlich solche zwei Sprachen. Da sie in N P sind , gibt es P TM M 1 und M 2 . Für alle Instanzen x L 1 ist die Menge aller Zertifikate Y x für T M 1 . In ähnlicher Weise definieren wir Z x ' für x 'L 2 . Da L 1 Karp auf L 2 reduzierbar ist , gibt es solche fL1L2NPM1M2xL1YxTM1ZxxL2L1L2fwie beschrieben.
cc
Nun haben wir neue M ' 1 und M ' 2 konstruiert . Für jede Instanz x L 1 ist die neue Menge aller Zertifikate 0 Y x + 1 Z f ( x ) , während für jede Instanz f ( x ) L 2 die neue Menge aller Zertifikate 0 Z f ( x ist ) + 1 x Y x . (Hier verwenden wir reguläre Ausdrücke.) Dies sind legale und alle Zertifikate fürM1M2xL10Yx+1Zf(x)f(x)L20Zf(x)+1xYxM ' 1 und M ' 2 . Übrigens, es gibt P Funktionen g und h wie definiert, die alle möglichen Zertifikate von einem Problem zum anderen transformieren. M1M2gh
cc
ps: Wir brauchen keine Transformation von x 'L 2 zu geben, wo es kein x L 1 gibt, so dass x ' = f ( x ) , da Karp- und Levin-Reduktionen beide viele zu einer Abbildung sind. Ich denke, das kann den vorletzten Absatz beantworten. xL2xL1x=f(x)
cc
@cc, es scheint, dass Sie immer noch denken, dass Sie die Verifizierer ändern können, Sie können nicht, die Definition der Levin-Reduktion ist für Suchprobleme, dh die Verifizierer sind behoben.
Kaveh
5

A quick counterexample for your proof: suppose that x1,x2L1x1,x2L1, f(x1)=f(x2)L2f(x1)=f(x2)L2, and ww is a valid certificate for x1x1 but not for x2x2

M1(x1,0,w)=M1(x1,w)=1M1(x1,0,w)=M1(x1,w)=1

M1(x2,0,w)=M1(x2,w)=0M1(x2,0,w)=M1(x2,w)=0

By definition g(x1,0,w)=1,x1,wg(x1,0,w)=1,x1,w

f(x1)=f(x2)f(x1)=f(x2) so M2(f(x2),1,x1,w))=M1(x1,w)=1 so 1,x1,w is a valid certificate for f(x2) but

h(f(x2),1,x1,w)=0,w which is not a valid certificate for x2

Vor
quelle
Thanks very much for pointing out the counterexample. I have modified the construction and I think it works now. Could you please have a look at it?
c c