¿Prueba de que el problema SAT no pertenece a P?

¿Prueba de que el problema SAT no pertenece a P?

de Juan Agustín Rivero Szwaicer -
Número de respuestas: 1
Hola. Me gustaría escribir un razonamiento para representar el problema de satisfacibilidad y que puede ayudar a darnos cuenta que (probablemente) no se puede resolver más que probando valores hasta llegar a la solución. El razonamiento sería el siguiente:

  • Una cláusula es una multiplicación de variables booleanas igualada a cero, donde el cero representa true. Ejemplo: xyz=0 si x=0 o y=0 o z=0, con x,y,z\in\{0,1\}
  • El problema de satisfacibilidad no es más que un sistema de ecuaciones donde cada ecuación es un producto de variables booleanas igualado a cero.
  • Para resolver este sistema de ecuaciones debemos de separar en casos, si cierta variable vale cero o si no.
  • Separar en casos es en otras palabras probar valores para las variables.
  • Por lo tanto el problema de satisfacibilidad no puede resolverse de otra forma que no sea probando valores hasta llegar a la solución.
  • Conclusión: el problema de satisfacibilidad no pertenece a P.

Nota: cuando separamos en casos no podríamos descartar ninguno de antemano porque para una situación del problema genérica todos los casos tienen "igual probabilidad" de aportar una solución.

No sé si realmente sea válido el razonamiento pero quería compartirlo por si llega a aportar algo jaja. Estaría bueno si pudieran hacerle alguna crítica o corrección, de todas formas no les quiero quitar mucho tiempo. Saludos
En respuesta a Juan Agustín Rivero Szwaicer

Re: ¿Prueba de que el problema SAT no pertenece a P?

de Carlos Testuri -
Hola Juan Agustín,

La relación entre el problema SAT y un sistema de ecuaciones la encuentras en el Ejercicio 1 del repartido de la Semana 16.
Probar que SAT no pertenece a la clase P, implica probar que no existe algoritmo de tiempo polinomial que resuelva SAT. O equivalentemente, probar que para todo algoritmo de tiempo polinomial no se resuelve SAT.
Creo que el último intento fallido publicado es el de Vinay Deolalikar.
Este año es el aniversario 70 del problema.
Al parecer se necesitarían nuevas herramientas para enfrentarlo.
¡ Tarea para las nuevas generaciones  !

Saludos,
Carlos Testuri