P versus NP

La relación entre las clases de complejidad P y NP es una pregunta que aún no se ha podido responder por la teoría de la complejidad computacional, cuyos recursos estudiados 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.

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 quién desarrolle la primera demostración correcta.