Reducir #SAT a # MONOTONE-2SAT

8

Se sabe que el problema # MONOTONE-2SAT es # P-completo. Esto significa que #SAT se puede reducir a eso. Mi pregunta es: dada una instancia #SAT , ¿cuál es la transformación que convierte F en su correspondiente instancia # MONOTONE-2SAT F ' ?FFF′

Una segunda pregunta es: que es el número de soluciones de F ' , y dejar que K es el número de soluciones de F . ¿ K ′ = K ? ¿O debemos usar una transformación inversa que convierta K ' a K ?K′F′KFK′=KK′K

cc.complexity-theory ds.algorithms complexity-classes sat Giorgio Camerani
fuente
¿Podría motivar por qué votó en contra de esta pregunta?
Giorgio Camerani
No fui yo quien votó la pregunta, pero no me sorprendería si alguien considera que la pregunta es demasiado básica.
Tsuyoshi Ito
No lo creo. No es más básico que algunas otras preguntas planteadas en este sitio web. De todos modos, una pregunta, aunque sea básica, puede ser útil. Mis preguntas sobre límites inferiores en #SAT y en los clústeres de soluciones SAT también pueden considerarse muy básicas, pero no fueron rechazadas.
Giorgio Camerani
La primera pregunta es bastante básica: esencialmente preguntaste qué era una reducción. La segunda pregunta también me ha atrapado una vez, pero se resuelve pensando de la manera correcta. El punto de mi respuesta es que la pregunta es fácil . Si aún cree que la pregunta está en el nivel correcto después de leer mi respuesta, probablemente mi respuesta esté mal escrita.
Tsuyoshi Ito
1
Walter, Tsuyoshi, aunque esta discusión es útil, un mejor lugar para ello es en meta.cstheory.stackexchange.com. ¿Por qué no discuten esto allí y agregan un enlace a esa discusión aquí? FWIW, creo que la pregunta es relativamente inofensiva, pero un poco más de "por qué pregunto" habría sido útil.
Suresh Venkat

Respuestas:

7

En cuanto a la primera pregunta, eso es lo que hace una reducción. Para saber cómo reducir # 3SAT a # Monotone-2SAT, consulte la prueba de # P-completitud de # Monotone-2SAT [Val79b], que se basa en # P-completitud de Permanente [Val79a]. Para reducir #SAT a # 3SAT, la reducción de Cook de cualquier problema en NP a 3SAT es parsimoniosa y, por lo tanto, reduce #SAT a # 3SAT.

La respuesta a la segunda pregunta es no. La reducción en [Val79a] de # 3SAT a Permanente no conserva el número de soluciones. Además, si se conoce una reducción de #SAT a # Monotone-2SAT (o Permanente) que conserva el número de soluciones, la misma reducción reduciría la versión de decisión de SAT a la versión de decisión de Monotone-2SAT (o Bipartite Matching), implicando P = NP.

Referencias

[Val79a] Leslie G. Valiant. La complejidad de cálculo de la permanente. Informática teórica , 8 (2): 189-201, 1979. http://dx.doi.org/10.1016/0304-3975(79)90044-6

[Val79b] Leslie G. Valiant. La complejidad de problemas de enumeración y fiabilidad. SIAM Journal on Computing , 8 (3): 410–421, agosto de 1979. http://dx.doi.org/10.1137/0208032

Tsuyoshi Ito
fuente
Gracias por sus sugerencias a [Val79b] y [Val79a]. En lo que respecta a la segunda respuesta, no puedo entenderlo: si un problema es # P-complete, puede usarse para resolver cualquier otro problema en #P. Ahora supongamos que quiero resolver #SAT: quiero saber el número K de soluciones de una fórmula dada F; para hacerlo, reduzco F a una instancia F 'de # MONOTONE-2SAT, luego obtengo el número K' de soluciones a F '. Ahora, si conocer K 'no me ayuda a conocer K (es decir, resolver # MONOTONE-2SAT no me ayuda a resolver #SAT) ¿cómo puede # MONOTONE-2SAT ser # P-completo? ¿Por qué debo hacer todo esto si no resuelve #SAT?
Giorgio Camerani
Déjame expresarte un comentario secundario. ¿Es posible que tenga que pagar 40 dólares para leer un artículo que tiene 31 años? Esto me parece absurdo y contra el espíritu de la ciencia. Estaría de acuerdo si el artículo tuviera entre 10 y 15 años, ya que puede considerarse como un descubrimiento "patentado". Pero pagar por un artículo de 31 años es una pena en mi humilde opinión. ¿Alguien podría señalarme una versión gratuita?
Giorgio Camerani
1
En cuanto a la segunda respuesta, es posible calcular K a partir de K '(y F); de lo contrario, un mapeo de F a F 'no sería una reducción. Sin embargo, su pregunta es sobre si es posible hacer una reducción tal que K = K '. La respuesta es que no es posible.
Tsuyoshi Ito
@ Tsuyoshi Ito: Un comentario adicional sobre su segunda respuesta. Tener el mismo número de soluciones no implica tener el mismo espacio de solución. Una instancia A puede tener el mismo número de soluciones de una instancia B, pero las soluciones de B pueden distribuirse de una manera completamente diferente en el espacio de la solución.
Giorgio Camerani
1
No conozco copias disponibles gratuitamente de los documentos que cité. Una prueba de la completitud # P de lo permanente se encuentra en muchos libros de texto sobre complejidad computacional, que pueden estar disponibles en las bibliotecas: por ejemplo, Complejidad computacional de Papadimitriou, Complejidad computacional: una perspectiva conceptual de Goldreich y Complejidad computacional: un enfoque moderno de Arora y Barak Contiene una prueba. (más)
Tsuyoshi Ito