## 3.2.3. LA CLASE DE COMPLEJIDAD NP

La complejidad computacional considera globalmente todos los posibles algoritmos para resolver un problema dado. Estamos interesados en la distinción que existe entre los problemas que pueden ser resueltos por un algoritmo en tiempo polinómico y los problemas para los cuales no conocemos ningún algoritmo polinómico, es decir, el mejor es no-polinómico.

La teoría de la NP-Completitud no proporciona un método para obtener algoritmos de tiempo polinómico, ni dice que que estos algoritmos no existan. Lo que muestra es que muchos de los problemas para los cuales no conocemos algoritmos polinómicos están computacionalmente relacionados.

La clase NP contiene numerosos problemas de importancia práctica. Típicamente el problema tiene que ver con la construcción o existencia de un objeto matemático que satisface ciertas especificaciones.

La versión de la construcción misma es un problema de optimizacion, donde la mejor construcción posible es la solución deseada. En la versión de decision, que es la versión que pertenece a la clase NP, la pregunta es si existe por lo menos una configuración que cumpla con los requisitos del problema.

Se puede decir que la mayoría de los problemas interesantes de computación en el mundo real pertenecen a la clase NP. La aplicación cotidiana de la teoría de complejidad computacional es el estudio sobre las clases a las cuales un dado problema pertenece: solamente a NP o tambien a P, o quizás a ninguna de las dos.

Mostrar que el problema de interés sea NP-completo, implicaría que el problema es entre los menos probables de pertenecer en la clase P. Si algún problema NP-completo perteneciera a NP, aplicaría NP = P.

###