¿Cómo puede un problema estar en NP, ser NP-hard y no NP-complete?

14

Durante mucho tiempo, pensé que un problema era NP-completo si es (1) NP-hard y (2) está en NP.

Sin embargo, en el famoso artículo "El método del elipsoide y sus consecuencias en la optimización combinatoria" , los autores afirman que el problema del número cromático fraccional pertenece a NP y es NP-duro, aunque no se sabe que sea NP completo. En la tercera página del artículo, los autores escriben:

... notamos que el problema de empaquetamiento de vértices de un gráfico es en un sentido equivalente al problema del número cromático fraccional, y comentamos sobre el fenómeno de que este último problema es un ejemplo de un problema en que es -hard pero (por ahora) no se sabe que -complete.nortePAGnortePAGnortePAG

¿Cómo es esto posible? ¿Me estoy perdiendo un detalle sutil en la definición de NP-complete?

cc.complexity-theory np-hardness complexity-classes terminology Austin Buchanan
fuente

Respuestas:

27

Parece que el problema es el tipo de reducciones utilizadas para cada una de ellas, y están usando diferentes: probablemente significan " -hard wrt Cook reductions" y " -complete wrt Karp reductions" .nortePAGnortePAG

A veces las personas usan la versión de reducción Cook de -hardness porque es aplicable a problemas computacionales más generales (no solo problemas de decisión). Aunque la definición original de -dureza y -completeness utilizaba reducciones de Cook (reducciones de Turing de tiempo polinomial), se ha vuelto poco común usar reducciones de Cook para -completeness (a menos que se establece explícitamente). No recuerdo ningún artículo reciente que haya utilizado -complete para significar -complete wrt Cook reductions. (Como nota al margen, el primer problema que debe probarse ennortePAGnortePAGnortePAGnortePAGnortePAGnortePAGnortePAG-Duro fue TAUT no SAT y la integridad de SAT está implícita en esa prueba).

Ahora, si mira la sección 7 del documento, al final de la página 195, verá que significan -hardness wrt Turing reductions.nortePAG

Entonces, lo que quieren decir aquí es que el problema está en , es difícil para las reducciones de wrt Cook, pero se desconoce que es difícil para las reducciones de wrt Karp (tiempo polinómico muchos -una reducción).nortePAGnortePAGnortePAG

Kaveh
fuente
1
¿Te refieres a DNF-Tautología por Taut? ¿No es eso CoNP completo? Porque CNF-Tautology es trivial.
Tayfun Pay
1
@TayfunPay: Probablemente Tautología para fórmulas arbitrarias, no solo CNF o DNF. Y Co-NP-complete y NP-complete es la misma reducción de Cook, que es la razón por la que Kaveh menciona esta anécdota.
frafl
1
@Tayfun, Cook lo prueba para fórmulas generales y lo usa DNF-TAUT es un corolario en el documento. Ambas son reducciones NP- hard wrt Cook.
Kaveh
@frafl, "NP-complete" se define en el artículo de Karp de 1972 . El artículo de Cook de 1971 define las reducciones de Cook y demuestra que TAUT es duro para NP. También demuestra que una serie de problemas son reducciones equivalentes de wrt Cook. Sin embargo, la complicidad de NP no se menciona explícitamente en el documento original.
Kaveh