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
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