¿Cuándo "X es NP-completo" implica "#X es # P-completo"?

Deje que denote un problema (decisión) en NP y deje que # denote su versión de conteo. $X$ $X$

¿En qué condiciones se sabe que "X es NP-completo" $\implies$ ¿"#X es # P-completo"?

Por supuesto, la existencia de una reducción parsimoniosa es una de esas condiciones, pero esto es obvio y la única condición de la que soy consciente. El objetivo final sería mostrar que no se necesita ninguna condición.

Hablando formalmente, uno debería comenzar con el problema de conteo # definido por una función y luego definir el problema de decisión en una cadena de entrada como ? $X$ $f : \{0,1\}^* \to \mathbb{N}$ $X$ $s$ $f(s) \ne 0$

cc.complexity-theory np-hardness counting-complexity Tyson Williams
fuente

¿Está buscando algo más que "X es NP-completo bajo reducciones parsimoniosas"?

Joshua Grochow

@usul: No. Si abandonamos la suposición de que X es NP-completo, entonces la coincidencia bipartita está en P (por lo que definitivamente no es NP-parsimoniosamente asumiendo

) pero su versión de conteo es # P-complete. Sin embargo, si realmente queremos X NP-complete, entonces no sé de un problema X tal que: 1) X sea NP-complete, 2) X no sea NP-complete bajo reducciones parsimoniosas, y 3) #X es # P-completo. Pero realmente no lo he pensado.

P \neq N P

$P \neq NP$

Joshua Grochow

¿Pero hay un problema que niega esto? es decir, X es NP-complete y #X no es # P-complete?

Suresh Venkat

@YoshioOkamoto: eso prueba que #X ∈ #P implica que X ∈ NP . Está en la dirección equivocada y pierde el problema de la integridad. Lo que estamos viendo esencialmente es qué requisitos adicionales son necesarios para la existencia de una reducción de muchos a uno para los problemas de decisión en NP (para problemas de decisión arbitrarios, o de un problema completo de NP ) implica la existencia de un reducción de conteo eficiente para problemas en #P (para problemas de conteo arbitrario, o de un problema completo #P ).

Niel de Beaudrap

@ColinMcQuillan Se podría decir a la inversa. Comience con un problema de conteo y defina un problema de decisión a partir de él preguntando si la salida no es cero.

Tyson Williams el

¿Cuándo "X es NP-completo" implica "#X es # P-completo"?

Respuestas: