A redução de Karp é idêntica à redução de Levin

12

Definição: Redução de Karp

Uma linguagem AA é Karp redutível a uma linguagem BB se houver uma função computável em tempo polinomial f : { 0 , 1 } { 0 , 1 } f:{0,1}{0,1} tal que para cada xx , x AxA se e somente se f ( x ) Bf(x)B .

Definição: Redução de Levin

Um problema pesquisa V UmaVA é Levin redutível a uma pesquisa problema V BVB se houver função polinomial ff que reduz Karp G ( V A )L(VA) a G ( V B )L(VB) e existem polinomial-tempo funções calculáveis gg e hh tal que

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

  2. F ( x ) , z V BX , h ( x , z ) V Umf(x),zVBx,h(x,z)VA

Essas reduções são equivalentes?


Eu acho que as duas definições são equivalentes. Para quaisquer dois N PNP idiomas AA e BB , se AA é Karp redutível para BB , então AA é Levin redutível a BB .

Aqui está a minha prova:

Deixe- x e ¯ x haver casos arbitrárias de um tempo x ' ser que de B . Suponha V A e V B são verificadores de A e B . Deixe- y e ¯ y ser certificados arbitrárias de x e ¯ x de acordo com V A . Deixe- z ser que de x ' de acordo com V B .xx¯¯¯AxBVAVBAByy¯¯¯xx¯¯¯VAzxVB

Construa novos verificadores V A e V B com novos certificados y e z :VAVByz

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

  1. Y ' = 0 , ¯ x , ¯ y : Se f ( x ) f ( ¯ x ) , rejeitar. Caso contrário, imprima V A ( ¯ x , ¯ y ) .y=0,x¯¯¯,y¯¯¯f(x)f(x¯¯¯)VA(x¯¯¯,y¯¯¯)
  2. Y ' = 1 , z : Saída V B ( f ( x ) , z ) .y=1,zVB(f(x),z)

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

  1. Z ' = 0 , z : Saída V B ( x ' , z ) .z=0,zVB(x,z)

  2. Z ' = 1 , x , y : Se X 'f ( x ) , rejeitar. Caso contrário, imprima V A ( x , y ) .z=1,x,yxf(x)VA(x,y)

As funções computáveis ​​em tempo polinomial g e h são definidas como abaixo:gh

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

  1. y=0,¯x,¯yy=0,x¯¯¯,y¯¯¯: Output 1,¯x,¯y1,x¯¯¯,y¯¯¯.

  2. y=1,zy=1,z: Output 0,z0,z.

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

  1. z=0,zz=0,z: Output 1,z1,z.

  2. z=1,x,yz=1,x,y: Output 0,x,y0,x,y.

Let YxYx be the set of all certificates of xx according to VAVA and ZxZx be the set of all certificates of xx according to VBVB. Then the set of all certificates of xx according to VAVA is 0¯xY¯x+1Zf(x)0x¯¯¯Yx¯¯¯+1Zf(x) such that f(x)=f(¯x)f(x)=f(x¯¯¯), and the set of all certificates of xx according to VBVB is 0Zx+1¯xY¯x0Zx+1x¯¯¯Yx¯¯¯ such that x=f(¯x)x=f(x¯¯¯).

(This is derived from the accepting language of VAVA and VBVB.)

Now let x=f(x)x=f(x), the rest part is easy to check.

c c
fonte
Before proving your claim, you should define what it means by a language being Levin reducible to another.
Tsuyoshi Ito

Respostas:

14

No. First note that Levin reduction only makes sense with respect to classes which certificate has a meaning, e.g. NPNP while Karp reduction is general. The word "certificate" for a problem makes sense only when a verifier is fixed. Levin's reduction assumes that the verifiers are fixed. You cannot change the verifiers. (In the following I assume that certificate verifiers are fixed as required by definition of Levin reduction.)

Second, Levin reduction means that one can find the certificate for one from the certificate for the other. It is true that the well-known Karp reductions between natural problems turn out to be Levin reduction but this does not need to be true in general.

If we can reduce instances of a problem AA to problem BB it doesn't mean we have a way of computing a certificate for one from a certificate for the other.

For this to be true we need the fact that a certificate search problem corresponding to the decision problem is polynomial time reducible to the decision problem. This is true for NP-completeNP-complete problems but not known to be true generally even for NPNP problems.

Kaveh
fonte
I agree on your first point that Karp reduction is more general than Karp reduction. According to it, I think my problem should be modified as "Let L1L1 and L2L2 be two languages in NPNP. If L1L1 is Karp reducible to L2L2, then L1L1 is Levin reducible to L2L2." However, I don't agree on your other comments.
c c
In my prove, first let L1L1 and L2L2 be arbitrary such two languages. Since they are in NP, there are P TM M1 and M2. For every instances xL1, the set of all certificates are Yx for TM1. Similarly, we define Zx for xL2. Since L1 is Karp reducible to L2, there is such f as defined.
c c
Now, we constructed new M1 and M2. For every instance xL1, the new set of all certificates are 0Yx+1Zf(x), while for every instance f(x)L2, the new set of all certificates are 0Zf(x)+1xYx.(Here we use regular expressions) These are legal and all certificates for M1 and M2. By the way, there is P functions g and h as defined transform all possible certificate from one problem to the other.
c c
ps: We don't need to give a transformation from xL2 where there is no xL1 such that x=f(x), since Karp and Levin reductions are both many to one mappings. I think this can answer the second last paragraph.
c c
@cc, it seems that you still think that you can change the verifiers, you cannot, the definition of Levin reduction is for search problems, i.e. the verifiers are fixed.
Kaveh
5

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

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

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

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

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
fonte
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