Práctico 11 - Ejercicio 2

Práctico 11 - Ejercicio 2

de Marco Liguori Hernandez -
Número de respuestas: 4

Buenas,

No estaría viendo por dónde encarar la reducción del 3-SAT a Al menos 2-SAT.

En el problema 3-SAT, ¿es permitido que las variables se repitan en las misma cláusulas?. O sea, una cláusula podría ser C = {x1 or x1 or x2}.

Cualquier ayuda se agradece,

Saludos.

En respuesta a Marco Liguori Hernandez

Re: Práctico 11 - Ejercicio 2

de Jonathan Murana -
Hola Marco, como estas?

Estuve leyendo el libro y la verdad no se si 3-SAT se permite repetir la misma variable sin negar, lo voy a seguir investigando y te contesto.

De todas formas intento darte una pista sin decirte la solución.

Se tiene que llevar una instancia genérica de 3-SAT a una instancia con alguna estructura particular de Al menos 2-SAT,
(que me sirva) para mostrar el si solo si:

Dado una instancia SI de 3-SAT (o sea que existe una asignacion de valores True/False a las variables de las clausulas
que hace True el conjunto de clausulas C, siendo C el conjunto de clausulas de la instancia genérica 3-SAT ) <=> la instancia construida de Al menos 2-SAT es SI (exiten al menos dos evaluaciones True para su conjunto de clausulas).

Y bueno, podes plantearte el directo: teniendo una instancia de 3-SAT y sabiendo que hay una asiginacion True
de su conjunto de clausulas C, de qué forma construir la instancia de a Al menos 2-SAT que me permita encontrar dos asignaciones True
facilmente para su conjunto de clausulas C'.


Espero que sirva el comentario
Saludos
En respuesta a Jonathan Murana

Re: Práctico 11 - Ejercicio 2

de Marco Liguori Hernandez -
Buenas Jonathan,

Lo que hice en base a lo que me dijiste y usando unos conceptos de libro fué básicamente agregar una cláusula C'i (con tres términos independientes que no estén ya en las cláusulas originales) al conjunto C de cláusulas de 3-SAT, tal que C'i tenga al menos dos asignaciones de verdad. Por lo tanto si se que la instancia de 3-SAT tiene al menos una asignación de verdad, entonces el conjunto C U C'i tendrá al menos dos asignaciones puesto que le estoy agregando una cláusula "independiente" con al menos dos asignaciones de verdad.

En base a esto demuestro que 3-SAT devuelve True sobre el conjunto C si y solo si Al menos 2-SAT devuelvé True sobre C U C'i.

¿Esto sería un camino válido o me perdí? ¿Tendría que ser explícito también en la negación del si y solo si, o sea explicitar que si una de las dos soluciones es False, la otra también?.

Gracias por tus respuestas y saludos,
Marco.
En respuesta a Marco Liguori Hernandez

Re: Práctico 11 - Ejercicio 2

de Jonathan Murana -
Sí, es un camino válido.

no hay que demostrar lo segundo que decis porque ya se demostraría. Fijate que si demostras el <=> tenes que demostrar el => y el <=, y si demostras ambas flechas, demostras ambos contrareciprocos.