Siguiente: Clases de problemas Un nivel arriba: COMPUTABILIDAD Y COMPLEJIDAD Anterior: Teorema de Borodin y

Completitud-NP

Comenzamos este capítulo con la presentación de diversas clases de problemas. Al caracterizar una clase, una noción fundamental es la de reducibilidad. Introduciremos luego a las clases de problemas tratables en tiempo y espacio polinomiales. Bien que el determinismo y el no-determinismo coinciden en diversos niveles de la Jerarquía de Chomski, tales como el de los lenguajes regulares y el de los lenguajes recursivos, desde el punto de vista computacional, la equivalencia de estas dos nociones plantea uno de los problemas clásicos en la actualidad: decidir si la clase de problemas resolubles en tiempo polinomial coincide con la clase de problemas comprobables en tiempo polinomial, es decir, decidir si acaso P=NP. Presentamos también las nociones de reducibilidad de problemas y con ello las de dificultad y completitud de problemas en una clase dada de problemas. Presentaremos el célebre teorema de Cook que asevera que el problema SAT de decidir si acaso una forma booleana es satisfactible, es completo en la clase NP. También veremos que restricciones de estos problemas a ciertos tipos de formas booleanas continúan siendo completos-NP.