Este problema, planteado de manera independiente en 1971 por Stephen Cook y por Leonid Levin se considera hoy dia el problema central de la computación teórica.

La cuestión es que existen, por una parte, problemas resolubles de manera determinista mediante algoritmos polinómicos y en un tiempo polinomial, como puede ser, por ejemplo la resolución de ecuaciones, la realización de sumas, productos, etc., pudiendo acotar el tiempo de resolución, mas o menos largo, de una manera aceptable. Estos son los problemas P.

Sin embargo, también existen problemas NP que pueden resolverse de forma indeterminista probando una solución conjeturada. Esta comprobación es de una gran rapidez en comparación con el tiempo polinomial necesario en general para la resolución determinista de los problemas P.

Está claro que todo problema P es también NP, esto es, todo problema resoluble en tiempo polinomial mediante un algoritmo adecuado (P), es también un problema que admite una comprobación rápida (NP).

Pero, ¿y al revés?. ¿Existen problemas NP que no sean P?. Esto es, ¿existen problemas que admiten una comprobación de solución o no solución conjeturada y, en cambio, no admiten en tiempo polinomial una resolución algoritmica?

En el cálculo computacional pueden presentarse problemas en donde el número de alternativas posibles para una determinada condición de proceso es tan grande que ni siquiera con las supercomputadores existentes aún en nuestra tecnología se podrían afrontar en toda la vida de un ser humano, pues no tendría para ello el suficiente tiempo (es el problema P). En cambio, la verificación de que una determinada alternativa verifica la condición de proceso es algo pràcticamente instantáneo (es el problema NP).

Si, por ejemplo, queremos colocar 6000 libros en 200 estantes, de modo que se cumpla la condición de que no estén juntos ciertos libros de diferente materia, nos encontramos que el número de alternativas posibles podría superar al número de átomos de la Vía Láctea, con lo cual, el determinarlas todas (problema P - difícil de encontrar) es precisamente eso, muy difícil en la actual tecnología de la computación. En cambio, el verificar una de estas alternativas como válida, cuando alguien conjetura una solución, (problema NP - fácil de verificar) es inmediato.

En estos ejemplos, en los que el problema NP es comprobable de inmediato, pero el problema P parece no existir, ¿se debe esto a que realmente el problema P no es posible o bien que no se tiene la tecnología computacional adecuada para su resolución de forma algoritmica en tiempo polinomial?

Esta es la pregunta no contestada que da consistencia al problema. Entre los ejemplos actuales más candentes está el de la criptografía y la comprobación de claves informaticas (NP) en contraposición al problema de generación algoritmica de tales claves en un tiempo polinomial (P).

__________________
"Aquel que es cruel con los animales se vuelve tosco en su trato con los hombres. Se puede juzgar el corazón de un hombre por su trato a los animales."
(Inmanuel Kant)