## 3.3 COMPLETITUD NP Y REDUCTIBILIDAD

Todos los algoritmos que se han visto hasta ahora han sido de tiempo polinomial, pero surge la duda o pregunta si de verdad todos los problemas se pueden resolver en tiempo polinomial, donde la respuesta más factible es un no. Por ejemplo, hay problemas, como el famoso “Problema de parada” de Turing, que no puede ser resuelto por ninguna computadora, sin importar cuánto tiempo debamos permitir. También hay problemas que pueden resolverse, pero no en tiempo polinomial.

En general, pensamos que los problemas que se pueden resolver mediante los algoritmos de tiempo polinomiales son fáciles de tratar, y los problemas que requieren que el tiempo superpolinomial sea intratable o difícil. Sin embarg, el estado de la clase de problemas, llamados NP-completos, es desconocido. Aún no se ha descubierto un algoritmo de tiempo polinomial para un problema NP.

Esta llamada pregunta de NP ha sido una de los más profundos y desconcertantes problemas de investigación abierta en la informática teórica desde que se planteó por primera vez en 1971. Varios problemas de NP-completos son particularmente tentadores porque parecen indicar que la superficie es similar a los problemas que sabemos resolver en tiempo de polinomios. En cada uno de los siguientes pares de problemas, uno se puede resolver en tiempo polinomial y otro es NP completo, pero la diferencia entre los problemas parece ser mínima:

- Rutas simples más cortas frente a las más largas: Es difícil encontrar un camino simple entre dos vértices. El simple hecho de determinar si un gráfico contiene una ruta simple con al menos un número determinado de aristas es NP-completo.
- Recorrido de crucero vs. Ciclo de Hamilton: Recorrido de un gráfico conectado, es un ciclo que atraviesa una parte de una vez, pero está permitido visitar cada vértice más de una vez.

Al caracterizar una clase, una noción fundamental es la de reducibilidad. 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.

###