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 .B x x ∈ A f ( x ) ∈ B
Definición: Reducción de Levin
Un problema de búsqueda es Levin reducible a un problema de búsqueda si hay una función de tiempo polinomial que Karp reduce a y hay funciones computables de tiempo polinomial y tales que
,
¿Son equivalentes estas reducciones?
Creo que las dos definiciones son equivalentes. Para cualquier par de lenguas y , si es reducible a Karp , entonces es reducible a Levin .
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 A A B y ¯ y x ¯ x V A z x ′ V B
Construya nuevos verificadores y con nuevos certificados y : V ′ B y ′ z ′
- f ( x ) ≠ f ( ¯ x ) V A ( ¯ x , ¯ y ) : Si , rechazar. De lo contrario, .
- V B ( f ( x ) , z ) : Salida .
V B ( x ' , z ) : Salida .
x ' ≠ f ( x ) V A ( x , y ) : Si , rechazar. De lo contrario, salida .
Las funciones computables de tiempo polinómico y se definen a continuación:h
⟨ 1 , ¯ x , ¯ y ⟩ : Salida .
⟨ 0 , z ⟩ : Salida .
⟨ 1 , z ⟩ : Salida .
⟨ 0 , x , y ⟩ : Salida .
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 ( x f(x)=f( ¯ x ) x ′ 0 Z x ′ + 1 ¯ x Y ¯ x x ′ = f ( ¯
(Esto se deriva del lenguaje de aceptación de y .) V ′ B
Ahora dejemos que , el resto es fácil de verificar.
Respuestas:
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.BA B
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-complete NP
fuente
Un contraejemplo rápido para su prueba: suponga que , , es un certificado válido para pero no parax1,x2∈L1 f(x1)=f(x2)∈L2 w x1 x2
Por definicióng(x1,⟨0,w⟩)=⟨1,x1,w⟩
x 2h(f(x2),⟨1,x1,w⟩)=⟨0,w⟩ que no es un certificado válido parax2
fuente