P vs np

P versus NP

Es sábado a la noche y acaba de llegar a una gran fiesta. Se siente tímido y se pregunta si conoce a alguien en la habitación.Su anfitrión sugiere que seguro conoce a Rose, la señorita al lado de la bandeja de postres. En una fracción de segundo usted echa un vistazo y se da cuentaque su anfitrión tenia razón. Aun así, gracias a esta sugerencia se vera obligado a hacer un tour por toda la habitación, chequeando persona por persona si hayalguien mas que conoce. Este es un ejemplo de que el fenómeno de generar una solución a un problema frecuentemente toma mas tiempo que verificar que unasolución es correcta.
Similarmente, si alguien le dice que el numero 13.717.421 puede ser escrito como el producto de dos números mas pequeños, ustedno sabe si creerle o no, pero si le dice que puede ser factoreado como 3607 por 3803 entonces puede fácilmente chequear si es cierto usando una simplecalculadora.
Uno de los mas sobresalientes problemas de la lógica y la ciencia de la computación es determinar si existen o no preguntas cuyasrespuestas pueden ser verificadas rápidamente (por ejemplo utilizando una computadora), pero puede requerir muchísimo mas tiempo resolverlas sin tener la solución.Ahí, ciertamente parece que están muchas de esas preguntas. Pero hasta el momento nadie ha probado que ninguna de ellas requiera de un largotiempo para su solución, puede ser que simplemente no hayamos descubierto como solucionarlas rápidamente. Stephen Cook formulo el problema de P versus NP en 1971.