Problema de P versus NP
El problema P versus NP es un problema importante sin resolver en la informática . Pregunta si todos los problemas cuya solución se puede verificar rápidamente también se pueden resolver rápidamente.
El término informal rápidamente , usado anteriormente, significa la existencia de un algoritmo que resuelve la tarea que se ejecuta en tiempo polinomial , de modo que el tiempo para completar la tarea varía como una función polinomial en el tamaño de la entrada al algoritmo (en contraposición a, digamos, tiempo exponencial ). La clase general de preguntas para las que algún algoritmo puede proporcionar una respuesta en tiempo polinomial es " P " o " clase P ". Para algunas preguntas, no existe una forma conocida de encontrar una respuesta rápidamente, pero si se proporciona información que muestre cuál es la respuesta, es posible verificar la respuesta rápidamente. La clase de preguntas para las que se puede verificar una respuesta.en tiempo polinomial es NP , que significa "tiempo polinomial no determinista". [Nota 1]
Una respuesta a la pregunta P versus NP determinaría si los problemas que se pueden verificar en tiempo polinomial también se pueden resolver en tiempo polinomial. Si resulta que P ≠ NP, que se cree ampliamente, significaría que hay problemas en NP que son más difíciles de calcular que de verificar: no podrían resolverse en tiempo polinomial, pero la respuesta podría verificarse en tiempo polinomial. .
Muchos consideran que el problema es el problema abierto más importante de la informática . [1] Además de ser un problema importante en la teoría computacional , una prueba de cualquier manera tendría profundas implicaciones para las matemáticas, la criptografía , la investigación de algoritmos, la inteligencia artificial , la teoría de juegos , el procesamiento multimedia, la filosofía , la economía y muchos otros campos. [2]
Es uno de los siete problemas del premio Millennium seleccionados por el Clay Mathematics Institute , cada uno de los cuales lleva un premio de US $ 1.000.000 por la primera solución correcta.
Considere el Sudoku, un juego en el que el jugador recibe una cuadrícula de números parcialmente completa e intenta completar la cuadrícula siguiendo ciertas reglas. Dada una cuadrícula de Sudoku incompleta, de cualquier tamaño, ¿existe al menos una solución legal? Cualquier solución propuesta se verifica fácilmente y el tiempo para verificar una solución crece lentamente (polinomialmente) a medida que la cuadrícula se hace más grande. Sin embargo, todos los algoritmos conocidos para encontrar soluciones requieren, para ejemplos difíciles, un tiempo que crece exponencialmente a medida que la cuadrícula se hace más grande. Entonces, Sudoku está en NP (se puede verificar rápidamente) pero no parece estar en P (se puede resolver rápidamente). Miles de otros problemas parecen similares, ya que son rápidos de comprobar pero lentos de resolver. Los investigadores han demostrado que muchos de los problemas en NP tienen la propiedad adicional de que una solución rápida a cualquiera de ellos podría usarse para construir una solución rápida a cualquier otro problema en NP.una propiedad llamadaNP-completitud . Décadas de búsqueda no han producido una solución rápida a ninguno de estos problemas, por lo que la mayoría de los científicos sospechan que ninguno de estos problemas puede resolverse rápidamente. Sin embargo, esto nunca se ha probado.
