Una diferencia significativa entre el análisis de algoritmos y la teoría de la complejidad computacional, es que el primero se dedica a determinar la cantidad de recursos requeridos por un algoritmo en particular para resolver un problema, mientras que la segunda, analiza todos los posibles algoritmos que pudieran ser usados para resolver el mismo problema.
Sin embargo, rápidamente se descubrió que el modelo básico de la máquina de Turing fallaba al cuantificar el tiempo y la memoria requerida por una computadora, un problema crítico hoy en día, y aún más en aquellos tiempos.
El campo comenzó a florecer cuando el investigador estadounidense Stephen Cook y el soviético Leonid Levin, trabajando de manera independiente, probaron que existen problemas relevantes que son NP-completos.
En 1972, Richard Karp llevó esta idea un paso más adelante, demostrando que 21 problemas combinatorios y de teoría de grafos, caracterizados por ser computacionalmente intratables, eran NP-completos.
[6] Un problema computacional constituye una pregunta a ser respondida, teniendo generalmente varios parámetros, o variables libres, cuyos valores no se han especificado.
Un problema de decisión pudiera verse como un lenguaje formal, donde los elementos que pertenecen al lenguaje son las instancias del problema cuya respuesta es "sí", los que no pertenecen al lenguaje son aquellas instancias cuya respuesta es "no".
El objetivo es decidir, con la ayuda de un algoritmo, si una determinada entrada es un elemento del lenguaje formal considerado.
Podemos decir informalmente, que los algoritmos son procedimientos paso-a-paso para resolver problemas.
Se puede pensar en ellos como simples programas de computadora, escritos en un lenguaje artificial específico.
De manera general, nos interesa encontrar el algoritmo más "eficiente" para resolver cierto problema.
Debido a que los requerimientos de tiempo son usualmente un factor dominante cuando se trata de determinar si un algoritmo es lo suficientemente eficiente para ser útil en la práctica, nos concentraremos en este recurso.
Las clases de complejidad más sencillas se definen teniendo en cuenta factores como: La clase P contiene a aquellos problemas resolubles en tiempo polinómico por una máquina de Turing determinista.
La clase P juega un papel importante en la teoría de la complejidad computacional debido a que: Muchas veces podemos evitar utilizar la fuerza bruta en los problemas para obtener soluciones en tiempo polinómico.
Quizás estos problemas tengan algoritmos en tiempo polinomial que se basan en principios por ahora desconocidos, o quizás estos problemas no pueden ser resueltos en tiempo polinómico, debido a que son "inherentemente difíciles".
Por verificable se entiende a un problema tal que dado un certificado de solución (candidato a solución), se puede verificar que dicho certificado es correcto en un tiempo polinómico en el tamaño de la entrada.
Al igual que la clase P, la clase NP es insensible a la elección del modelo de cómputo no determinista, debido a que dichos modelos son equivalentes polinómicamente.
Muchas clases de complejidad importantes pueden ser definidas acotando el tiempo o el espacio utilizado por el algoritmo.
La mayoría de los investigadores cree que estas clases no son iguales, porque se ha realizado bastantes esfuerzos, sin éxito, para encontrar algoritmos de tiempo polinomial para varios problemas en NP.
Los investigadores también han tratado de probar que las clases son distintas, pero eso conllevaría a mostrar que no existe un algoritmo «eficiente» para reemplazar a la búsqueda por fuerza bruta.
Esta clase tiene la curiosa propiedad de que si algún problema NP-completo puede ser resuelto en tiempo polinomial, entonces todo problema en NP tiene una solución en tiempo polinomial, es decir, P=NP.
Si algún problema en NP requiere más que un tiempo polinomial, entonces uno NP-completo también.
Además, un investigador intentando demostrar que P=NP, solo necesita encontrar un algoritmo de tiempo polinomial para un problema NP-completo para lograrlo.