P vs. NP - En busca del algoritmo "imposible" para 3SAT

Haciendo uso de nuestra metodología basada en las abstracciones exponenciales, abordamos el diseño de un algoritmo polinómico para el problema 3-SAT. Si parafraseáramos a Lance Fortnow, podríamos decir que nos embarcamos en la búsqueda de lo imposible.

El algoritmo teóricamente polinómico (de orden cuartico) que mostramos nos valió para reforzar nuestra teoría, y considerar que a pesar de que pudieran demostrarse que existen limiten físicos (P != NP) que condicionan y condicionaran por siempre el diseño de algoritmos, sería posible usar la abstracción como un recurso computacional más. Este recurso, que es independiente al espacio y el tiempo podría tender a crecer exponencialmente a pesar de que los recursos temporales y espaciales que usará nuestra máquina de cómputo se mantuvieran acotados en términos polinómicos.

En este libro, podrá ver como gracias al uso de la abstracción y del diseño de algoritmos, podemos computar todo el conjunto de configuraciones satisfacibles de una instancia 3-SAT, y posteriormente, en caso de el conjunto no sea vacío, leer una de ellas como certificado de satisfacibilidad. Al igual que hacíamos, en nuestro trabajo de investigación, para computar de forma abstracta el conjunto de todos ciclos hamiltonianos o tours de TSP.

Somos conscientes del escepticismo generalizado que existe alrededor de cualquier intento de diseñar un algoritmo polinómico para un problema NP-Complete como es 3-SAT. Sin embargo, le invitamos a dar a este algoritmo (para 3-SAT) y a nuestros otros algoritmos (para HC, TSP, n-Queens) el beneficio de la duda. De hecho, podemos decir que la lógica de este algoritmo es mucho más simple (y, por ende, más fácil de entender) que la que requerimos implementar en nuestro trabajo principal para HC y TSP.