Verificando soluciones únicas de SAT

25

Considere el siguiente problema: dada una fórmula CNF y una asignación que satisface esta fórmula, ¿hay otra asignación satisfactoria para esta fórmula?

¿Cuál es la complejidad de este problema? (Seguramente está en NP, pero ¿también es NP-hard?)

¿Qué sucede si no se le asigna la tarea y solo desea decidir si la fórmula tiene una tarea satisfactoria única?

Gracias.

cc.complexity-theory np-hardness sat unique-solution J--
fuente
13
Su primer problema es a menudo un ejercicio de tarea. Sugerencia: dada cualquier fórmula F, diseñe una fórmula F 'donde la asignación de todos los ceros la satisfaga trivialmente, y exista una segunda asignación satisfactoria F' si F es satisfactoria.
Ryan Williams
1
@ Hsien-Chih Chang, teníamos el nombre de Oded en la portada antes de que volviera a etiquetar, no es urgente volver a etiquetar, sería bueno que su nombre permaneciera allí un poco más. :)
Kaveh
1
@Kaveh: Vaya, lo siento. Supongo que de alguna manera supongo que se quedará y constantemente proporcionará más y más buenas respuestas, por lo que su nombre aparecerá con frecuencia en la página principal :)
Hsien-Chih Chang 張顯 之
@ Hsien-Chih Chang, también espero que sí. :)
Kaveh

Respuestas:

27

El problema de decidir si una fórmula CNF dada tiene una asignación satisfactoria diferente de una determinada se muestra fácilmente como NP completa al transformar una fórmula CNF para agregar una solución trivial. Este problema se denomina "Otro problema de solución (ASP) de SAT" en [YS03], donde se utiliza para proporcionar una prueba sistemática de que (las versiones de decisión de) las ASP de muchos otros problemas también están NP completas.

El problema de decidir si una fórmula CNF dada tiene una asignación satisfactoria única o no (por lo que debe responder "no" si la fórmula no tiene asignaciones satisfactorias o más de una asignación satisfactoria) es un problema de Estados Unidos . US contiene UP y coNP .

Referencias

[YS03] Takayuki Yato y Takahiro Seta. Complejidad e integridad de encontrar otra solución y su aplicación a los rompecabezas. Transacciones de IEICE sobre fundamentos de electrónica, comunicaciones y ciencias de la computación, E86-A (5): 1052-1060, mayo de 2003.

Editar : una versión anterior (revisión 1) de esta respuesta contenía una confusión entre la versión de decisión y la versión de búsqueda. Ha sido arreglado.

Tsuyoshi Ito
fuente
66
Solo una nota: la integridad de NP de "otro problema de solución" es el folklore, conocido mucho antes de 2003. (Tal vez hay una referencia de la década de 1970, pero la prueba es tan fácil que lo dudo)
Ryan Williams
@ Ryan: Gracias por la nota. Edité la respuesta para aclarar la relación con [YS03].
Tsuyoshi Ito
22

Recuerdo que Yoram Moses y yo estudiamos este problema a mediados de la década de 1980 (a la luz de alguna aplicación) y descubrí que para muchos problemas naturales de NPC el problema de encontrar una segunda solución alternativa (o decidir si existe) es NPC. Luego descubrimos que esto era conocido, pero no recuerdo la referencia, y no pude encontrar una (es decir, una anterior a mediados de la década de 1980) ahora. Pero estoy seguro de que recuerdo correctamente lo anterior.

Solo un comentario hacia Ryan. El hecho de que se pueda dar un teorema como ejercicio en las clases actuales no lo hace menos atractivo. Debería haberse publicado en un documento con un título adecuado en el momento en que se descubrió ...

Oded Goldreich

Oded Goldreich
fuente
15
¡Hola, bienvenido a bordo! Estoy muy emocionado de verte aquí :)
MS Dousti
12

Aquí, escribo un extracto del siguiente artículo:

Valiant, LG y Vazirani, VV 1986. NP es tan fácil como detectar soluciones únicas. Theor Comput Sci. 47, 1 (noviembre de 1986), 85-93. DOI = http://dx.doi.org/10.1016/0304-3975(86)90135-0

Para cada problema NP-completo conocido, el número de soluciones de sus instancias varía en un amplio rango, desde cero hasta exponencialmente muchas. Por lo tanto, es natural preguntarse si la intractabilidad inherente del problema NP-completo es causada por esta amplia variación. Damos una respuesta negativa a esta pregunta utilizando la noción de reducibilidad de tiempo polinomial aleatorio. Mostramos que los problemas de distinguir entre instancias de SAT que tienen cero o una solución, o de encontrar soluciones a instancias de SAT que tienen una solución única, son tan difíciles como SAT, bajo reducciones aleatorias.

También sugiero mirar el artículo relevante:

Beigel, R., Buhrman, H. y Fortnow, L. 1998. NP podría no ser tan fácil como detectar soluciones únicas. En las actas del trigésimo simposio anual de ACM sobre teoría de la computación (Dallas, Texas, Estados Unidos, 24 al 26 de mayo de 1998). STOC '98. ACM, Nueva York, NY, 203-208. DOI = http://doi.acm.org/10.1145/276698.276737

MS Dousti
fuente
6

rePAGS={(L1∩L2)El |L1∈nortePAGS,L2∈doonortePAGS} (la intersección del conjunto NP con el conjunto Co-NP).

Andreas Blass y Yuri Gurevich, Sobre el problema único de la satisfacción,

Mohammad Al-Turkistany
fuente
1
Un pequeño punto: el segundo problema no es un problema de promesa.
Tsuyoshi Ito
1
Me di cuenta de eso y lo arreglé, ¡pero gracias por verlo de todos modos!
Tsuyoshi Ito
66
Por cierto, no copié nada de su respuesta, por lo que no tengo idea de a qué se refiere su siguiente comentario: "Cuando copie de otra respuesta, indíquelo". Copié la referencia de mi respuesta de otra publicación mía. en MathOverflow ( mathoverflow.net/questions/31251/… ), pero no creo que se esté refiriendo a esto.
Tsuyoshi Ito