¿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 } y τ : { 0 , 1 } ∗ × N → N 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.
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).
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?
Respuestas:
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.ϕ ψ
fuente