¿Contando la reducción de #SAT a #HornSAT?

8

¿Es posible encontrar una reducción de conteo de #SAT a #HornSAT? No he encontrado esta pregunta publicada aquí, así que decidí verificar si alguien tiene alguna respuesta. Permítanme explicar a qué me refiero con contar la reducción.

Suponga que son dos problemas de conteo. Por ejemplo, #SAT pregunta cuántas asignaciones satisfactorias hay para una instancia específica ϕ , y f , g son problemas de conteo similares para encontrar el número total de testigos. Una reducción de conteo débilmente parsimoniosa de f a g consiste en un par de funciones computables de tiempo polinomial σ : { 0 , 1 } { 0 , 1 }f,g:{0,1}Nϕf,gfg y τ : { 0 , 1 } × NN tal que f ( x ) = τ ( x , g ( σ ( x ) ) ) . En el caso de que f ( x ) = g ( σ ( x ) ) , esto se conoce como reducción de recuento muy parsimoniosa.σ:{0,1}{0,1}τ:{0,1}×NNf(x)=τ(x,g(σ(x)))f(x)=g(σ(x))

Puedo ver que si hay una reducción de conteo de #SAT a #HornSAT, debe ser una reducción débilmente parsimoniosa: una reducción fuerte implicaría que las instancias #SAT y #HornSAT tendrán un número cero o no cero de soluciones juntas, y suponiendo que , esto es imposible (como HornSAT P mientras SAT es N P -completo).PNPPNP

Entonces mi pregunta es: ¿hay alguna reducción de conteo débilmente parsimoniosa de #SAT a #HornSAT? Si es así, ¿alguien puede darme alguna referencia?

David
fuente
2
"#HornSAT es # P-complete" significa que cada problema de #P puede reducirse a #HornSAT mediante una reducción de conteo (débilmente parsimoniosa).
Tsuyoshi Ito
1
¿Qué significa débilmente vs fuertemente parsimonioso?
Huck Bennett
@Huck Bennett ... He mencionado la definición matemática en la pregunta. Informalmente podemos decir que una fuerte reducción significa que ambos problemas tienen el mismo número de soluciones. Reducción débil significa que se puede encontrar el número de soluciones de la instancia del problema original en tiempo polinómico a partir del número de soluciones de la instancia del problema reducido.
David
@ TsuyoshiIto ... correcto, significa que debe haber una reducción de conteo (débilmente parsimoniosa) de #SAT a #HornSAT. Quiero saber esa reducción. No he encontrado ninguna reducción directa o indirecta. Básicamente no sé cómo demostrar "#HornSAT es # P-completo". Puede ser que no soy tan bueno en la búsqueda de Google. Cualquier referencia?
David

Respuestas:

10

Esta publicación discute # P-completitud de # Monotone-2SAT bajo reducciones débilmente parsimoniosas. Si niega todos los literales en una fórmula monótona 2-CNF , obtendrá una fórmula Horn 2-CNF ψ con el mismo número de asignaciones satisfactorias.ϕψ

Radu Curticapean
fuente
1
Muchas gracias por el puntero. Realmente me ayuda mucho. :)
David