supongamos que usted está organizando alojamiento para un grupo de cuatrocientos estudiantes universitarios. El espacio es limitado y solo cien de los estudiantes recibirán plazas en el dormitorio. Para complicar las cosas, el decano le ha proporcionado una lista de pares de estudiantes incompatibles, y solicitó que ningún par de esta lista aparezca en su elección final., Este es un ejemplo de lo que los científicos informáticos llaman un problema NP, ya que es fácil verificar si una determinada elección de cien estudiantes propuesta por un compañero de trabajo es satisfactoria (es decir, ningún par tomado de la lista de su compañero de trabajo también aparece en la lista de la Oficina del Decano), sin embargo, la tarea de generar una lista de este tipo desde cero parece ser tan difícil como para ser completamente impráctico. De hecho, el número total de formas de elegir cien estudiantes de los cuatrocientos solicitantes es mayor que el número de átomos en el universo conocido!, Por lo tanto, ninguna civilización futura podría esperar construir una supercomputadora capaz de resolver el problema por la fuerza bruta; es decir, comprobando cada combinación posible de 100 estudiantes. Sin embargo, esta aparente dificultad solo puede reflejar la falta de ingenio de su programador. De hecho, uno de los problemas pendientes en la informática es determinar si existen preguntas cuya respuesta se puede comprobar rápidamente, pero que requieren un tiempo imposiblemente largo para resolver por cualquier procedimiento directo., Problemas como el mencionado anteriormente ciertamente parecen ser de este tipo, pero hasta ahora nadie ha logrado demostrar que ninguno de ellos realmente son tan difíciles como parecen, es decir, que realmente no hay una manera factible de generar una respuesta con la ayuda de un ordenador. Stephen Cook y Leonid Levin formularon el problema P (es decir, fácil de encontrar) versus NP (es decir, fácil de verificar) de forma independiente en 1971.crédito de la imagen: a la izquierda, Stephen Cook de Jiří Janíček (recortado). CC BY-SA 3.0