La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder. En esencia, la pregunta <<¿es P = NP completo?>> significa: <<Si es posible "verificar" rápidamente las soluciones de un problema (es decir, es un problema de tipo NP), ¿eso implica que también es posible "obtener" las respuestas con la misma rapidez? (es decir, es un problema de tipo P)>>, donde "rápidamente" significa "en tiempo polinómico".
Los recursos comúnmente estudiados en complejidad computacional son:
– El tiempo: mediante una aproximación al número de pasos de ejecución que un algoritmo emplea para resolver un problema.
– El espacio: mediante una aproximación a la cantidad de memoria utilizada para resolver el problema.
Los problemas se clasifican en conjuntos o clases de complejidad (L, NL, P, PCompleto, NP, NP-Completo, NP Duro...). Este artículo se centrará en las clases P y NP.
Se considera el problema más importante en este campo, el Clay Mathematics Institute ha ofrecido un premio de un millón de dólares estadounidenses para quien desarrolle la primera demostración correcta.