Prog3: Ejercicio 2 semana 15

Buenas.

Haciendo este ejercicio me surgió la siguiente duda. Al momento de probar que 3-SAT es polinomialmente reducible a AL MENOS 2-SAT lo que estaba intentando hacer era probar que una instancia arbitraria de 3-SAT se puede modelar como una instancia para el segundo, lo que me está generando duda es que que el algoritmo de AL MENOS 2-SAT retorne “no” significa qué hay una valuación o menos, pero eso no me permite concluir que no hay valuación para 3-SAT que es lo que me gustaría poder concluir (para poder concluir el sii)

Quizá lo estoy pensando mal. Agradezco si me ayudan a sacarme esa duda así termino el ej.

Saludos!!

Re: Ejercicio 2 semana 15

de Juan Pablo Martinez Delbugio - martes, 16 de noviembre de 2021, 00:05

Buenas,

Entiendo que tenés un algoritmo que recibe una instancia de 3-SAT y querés probar que, si hay una asignación que satisface la instancia recibida (la colección de cláusulas), el algoritmo retorna true.

Utilizando la misma instancia que recibís e invocando a un algoritmo que resuelve AL MENOS 2-SAT, no lo vas a poder lograr (justamente por lo que decis, que una instancia de 3-SAT se pueda satisfacer no significa que la misma instancia se pueda satisfacer al menos dos veces).

Te recomiendo modificar la instancia de 3-SAT para que, si la original tiene una asignación válida, la nueva instancia tenga al menos 2 (manteniendo el recíproco: si la nueva tiene al menos 2, la anterior tiene al menos una).

Saludos,
JP