Teoria de complejidad computaional

Concepto de complejidad de algoritmo
Es la parte de la teoría de la computación que estudia los recursos necesarios durante el cálculo para resolver un problema.
Estos recursos son: el tiempo y el espacio.
-Clases de complejidad.
Los problemas de decisión (aquellos donde las respuesta es si o no) se clasifican en conjunto de complejidad comparable que son llamados clases de complejidad.
a) Clase de complejidad P: Es el conjunto de los problemas de decisión que pueden ser resueltos en tiempo polinomio por una maquina de turins lo que corresponde a problemas que pueden ser resueltos aun en el peor de los casos
Ej. Camino optimo de un cartero, saber si un número entero es primo, decidir si una frase pertenece a un conjunto dado de frases.
b) Clase de complejidad NP: conjunto de los problemas de decisión que pueden ser determinados por una maquina de turins no determinista en tiempo polinomio. Los problemas de esta clase tienen la propiedad de que su solución puede ser verificada.
Ej. El problema del agente viajero, El problemas de satisfacción booleana.
c) Clase de complejidad NP-Completo: Es el subconjunto de los problemas de decisión de Np que destacan por su extrema complejidad y que decimos que se hayan en la frontera externa de la clase NP.
Ej. La suma de subconjuntos dado un conjunto S de enteros, ¿existe un subconjunto no dado cuyos elementos sumen 0?, ¿Dos grafos son isomórficos si se puede transformar uno en el otro simplemente renombrando sus vértices?

¿Las clases P y Np son diferentes o no?
El Clay Mathematics Institute ofrece 1 millón de dólares a quien sea capaza de responder satisfactoriamente a esa pregunta.