¿Es Karp Reduction idéntica a Levin Reduction?

12

Definición: Reducción de Karp

Un lenguaje es Karp reducible a un lenguaje si hay una función computable de tiempo polinomial f: \ {0,1 \} ^ * \ rightarrow \ {0,1 \} ^ * tal que para cada x , x \ in a si y sólo si f (x) \ in B .BAB x x A f ( x ) Bf:{0,1}{0,1}xxAf(x)B

Definición: Reducción de Levin

Un problema de búsqueda VA es Levin reducible a un problema de búsqueda VB si hay una función de tiempo polinomial f que Karp reduce L(VA) a L(VB) y hay funciones computables de tiempo polinomial g y h tales que

  1. x,yVAf(x),g(x,y)VB ,

  2. f(x),zVBx,h(x,z)VA

¿Son equivalentes estas reducciones?


Creo que las dos definiciones son equivalentes. Para cualquier par de NP lenguas A y B , si A es reducible a Karp B , entonces A es reducible a Levin B .

Aquí está mi prueba:

Deje y sea instancias arbitrarias de , mientras que sea la de . Supongamos y son verificadores de y . Deje que y sean certificados arbitrarios de y acuerdo con . Sea el de acuerdo con .¯ x A x B V Axx¯AxBVA A B y ¯ y x ¯ x V A z x V BVBAByy¯xx¯VAzxVB

Construya nuevos verificadores y con nuevos certificados y : V B y z VAVByz

VA(x,y):

  1. f ( x ) f ( ¯ x ) V A ( ¯ x , ¯ y )y=0,x¯,y¯ : Si , rechazar. De lo contrario, .f(x)f(x¯)VA(x¯,y¯)
  2. V B ( f ( x ) , z )y=1,z : Salida .VB(f(x),z)

VB(x,z):

  1. V B ( x ' , z )z=0,z : Salida .VB(x,z)

  2. x 'f ( x ) V A ( x , y )z=1,x,y : Si , rechazar. De lo contrario, salida .xf(x)VA(x,y)

Las funciones computables de tiempo polinómico y se definen a continuación:hgh

g(x,y)

  1. 1 , ¯ x , ¯ yy=0,x¯,y¯ : Salida .1,x¯,y¯

  2. 0 , z y=1,z : Salida .0,z

h(x,z)

  1. 1 , z z=0,z : Salida .1,z

  2. 0 , x , y z=1,x,y : Salida .0,x,y

Sea el conjunto de todos los certificados de según y sea ​​el conjunto de todos los certificados de según . Entonces, el conjunto de todos los certificados de según es tal que , y el conjunto de todos los certificados de según es modo que . x V A Z x x V B x V A 0 ¯ x Y ¯ x + 1 Z f ( xYxxVAZxxVBxVA f(x)=f( ¯ x ) x 0x¯Yx¯+1Zf(x)f(x)=f(x¯)x 0 Z x + 1 ¯ x Y ¯ x x = f ( ¯VB0Zx+1x¯Yx¯x=f(x¯)

(Esto se deriva del lenguaje de aceptación de y .) V BVAVB

Ahora dejemos que , el resto es fácil de verificar.x=f(x)

cc
fuente
Antes de probar su reclamo, debe definir qué significa que un lenguaje sea Levin reducible a otro.
Tsuyoshi Ito

Respuestas:

14

No. Primero tenga en cuenta que la reducción de Levin solo tiene sentido con respecto a las clases cuyo certificado tiene un significado, por ejemplo, mientras que la reducción de Karp es general. La palabra "certificado" para un problema solo tiene sentido cuando se corrige un verificador. La reducción de Levin supone que los verificadores son fijos. No puedes cambiar los verificadores. (A continuación, supongo que los verificadores de certificados se arreglan según lo requerido por la definición de reducción de Levin).NP

En segundo lugar, la reducción de Levin significa que uno puede encontrar el certificado para uno del certificado para el otro. Es cierto que las conocidas reducciones de Karp entre problemas naturales resultan ser la reducción de Levin, pero esto no tiene por qué ser cierto en general.

Si podemos reducir las instancias de un problema al problema , no significa que tengamos una manera de calcular un certificado para uno de un certificado para el otro.BAB

Para que esto sea cierto, necesitamos el hecho de que un problema de búsqueda de certificados correspondiente al problema de decisión es un tiempo polinómico reducible al problema de decisión. Esto es cierto para los problemas , pero no se sabe que sea cierto en general, incluso para los problemas .N PNP-completeNP

Kaveh
fuente
Estoy de acuerdo en su primer punto de que la reducción de Karp es más general que la reducción de Karp. De acuerdo con ella, creo que mi problema debe ser modificado como "Let y dos idiomas en . Si es reducible a Karp , entonces es reducible a Levin ." Sin embargo, no estoy de acuerdo con sus otros comentarios. L 2 N P L 1 L 2 L 1 L 2L1L2NPL1L2L1L2
cc
En mi demuestran, primero vamos y ser arbitraria dichos dos idiomas. Como están en , hay P TM y . Para cada instancia , el conjunto de todos los certificados son para . Del mismo modo, definimos para . Como es Karp reducible a , existe tal como se define. L1L2NPM1M2xL1YxTM1ZxxL2L1L2f
cc
Ahora, construimos nuevos y . Para cada instancia , el nuevo conjunto de todos los certificados es , mientras que para cada instancia , el nuevo conjunto de todos los certificados es . (Aquí usamos expresiones regulares) Estos son legales y todos los certificados para y . Por cierto, hay funciones P y tal como se define a transformar todo certificado posible de un problema a la otra. M1M2xL10Yx+1Zf(x)f(x)L20Zf(x)+1xYxM1M2gh
cc
ps: No necesitamos dar una transformación de donde no hay modo que , ya que las reducciones de Karp y Levin son asignaciones de muchos a uno. Creo que esto puede responder el segundo último párrafo. xL2xL1x=f(x)
cc
@cc, parece que todavía piensa que puede cambiar los verificadores, no puede, la definición de reducción de Levin es para problemas de búsqueda, es decir, los verificadores son fijos.
Kaveh
5

Un contraejemplo rápido para su prueba: suponga que , , es un certificado válido para pero no parax1,x2L1f(x1)=f(x2)L2wx1x2

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

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

Por definicióng(x1,0,w)=1,x1,w

f(x1)=f(x2) entonces entonces es un certificado válido para peroM2(f(x2),1,x1,w))=M1(x1,w)=11,x1,wf(x2)

x 2h(f(x2),1,x1,w)=0,w que no es un certificado válido parax2

Vor
fuente
Muchas gracias por señalar el contraejemplo. He modificado la construcción y creo que funciona ahora. ¿Podrías echarle un vistazo?
cc