¿Podemos construir una reducción de Karp a partir de una reducción de Cook entre problemas de NP?

10

Hemos tenido varias preguntas sobre la relación de las reducciones de Cook y Karp . Está claro que las reducciones de Cook (reducciones de Turing de tiempo polinómico) no definen la misma noción de integridad de NP que las reducciones de Karp (reducciones de tiempo múltiple polinomiales), que generalmente se usan. En particular, las reducciones de Cook no pueden separar NP de co-NP incluso si P NP. Por lo tanto, no debemos usar reducciones de Cook en pruebas de reducción típicas.

Ahora, los estudiantes encontraron un trabajo revisado por pares [1] que utiliza una reducción de Cook para mostrar que un problema es NP-difícil. No les di la puntuación completa por la reducción que tomaron desde allí, pero me pregunto.

Ya que las reducciones de cocinero hacen definir una noción similar de dureza como reducciones Karp, siento que debe ser capaz de separar P de la APN resp. co-NPC, suponiendo P NP. En particular, (algo así) lo siguiente debería ser cierto:

.L1NP,L2NPCKarp,L2CookL1L1NPCKarp

La pepita importante es que así que se anula la insensibilidad mencionada anteriormente. Ahora "sabemos", por definición de NPC, que L 2 K a r p L 1 .L1NPL2KarpL1

Como ha notado Vor , no es tan fácil (notación adaptada):

L1NPCCookL2NPCKarpNPL2CookL1L1NPCKarpNPCKarp=NPCCook

Puede haber otras diferencias entre los dos NPC pero co-NP.

P

L2NPCKarp,L2CookL1,P(L1,L2)L1NPCKarp


  1. Sobre la complejidad de la alineación de secuencias múltiples por L. Wang y T. Jiang (1994)
Rafael
fuente
NPCKarp=NPCCookNP
PL1NPP

Respuestas:

4

es un problema de TCS generalmente abierto sujeto a una investigación en curso sobre si las condiciones exactas y las reducciones de Cook y Karp son equivalentes y aparentemente está estrechamente relacionado con la pregunta abierta NP =? coNP y otras separaciones de clase de complejidad, por ejemplo, E =? NE (wrt idiomas dispersos).

Aquí hay dos trabajos de investigación sobre el tema y más pistas sobre tcs.se a través de una pregunta similar:

vzn
fuente
No estoy buscando la relación exacta .
Raphael
1

En general, para convertir mecánicamente un problema de Cook-complete en un problema de Karp-complete, debe haber algo especial con el lenguaje en sí.

L

L

xx=f(x)L(x)L(x)

g(x)f(g(x))

Como puede ver, estas propiedades normalmente no se ven en la teoría de la complejidad, la teoría de la computabilidad. En conclusión, es extremadamente improbable poder convertir a Cook en Karp.

Thinh D. Nguyen
fuente