Hola! Quería saber si el siguiente planteo es correcto. Me queda más bien la duda para la primera parte: transformar 3-Sat en Almenos 2-Sat. No sé si lo que escribo es suficiente para afirmar que la transformación de una instancia a la otra se hace en tiempo polinomial, es decir, me parece una transformación muy "directa" como para entrar en detalle de tiempos, aunque tal vez es necesario. Gracias!!
Buenas,
Lo primero que veo de tu solución es que no queda clara la definición de
cuando decís "tomo un término que no pertenezca a C'". 3-SAT está definido por dos conjuntos: las cláusulas C, y los términos X. El término debería ser agregado en X, mientras que la nueva cláusula que planteas se agrega a C. Por otro lado, para explicar que la transformación es lineal basta con observar que solo hay que copiar la primera instancia 
y agregarle un único término a cada conjunto (tiempo constante).
Respecto a la demostración, de nuevo se mezclan los conceptos de X y C. En el directo, habría que tomar como hipótesis que existe una asignación de verdad a los elementos de X que satisface C', y concluir que en Al menos 2-SAT hay 2 asignaciones de verdad satisfactorias. Esas asignaciones de verdad tienen que ser explícitas y se debe justificar por qué satisfacen C. Algo similar sucede con el recíproco.
Cualquier duda volvé a consultar.
Saludos,
Guillermo
Lo primero que veo de tu solución es que no queda clara la definición de
cuando decís "tomo un término que no pertenezca a C'". 3-SAT está definido por dos conjuntos: las cláusulas C, y los términos X. El término debería ser agregado en X, mientras que la nueva cláusula que planteas se agrega a C. Por otro lado, para explicar que la transformación es lineal basta con observar que solo hay que copiar la primera instancia y agregarle un único término a cada conjunto (tiempo constante). Respecto a la demostración, de nuevo se mezclan los conceptos de X y C. En el directo, habría que tomar como hipótesis que existe una asignación de verdad a los elementos de X que satisface C', y concluir que en Al menos 2-SAT hay 2 asignaciones de verdad satisfactorias. Esas asignaciones de verdad tienen que ser explícitas y se debe justificar por qué satisfacen C. Algo similar sucede con el recíproco.
Cualquier duda volvé a consultar.
Saludos,
Guillermo