23/11/07

Un Problema De Un Millón De Dólares


Es sábado en la noche y usted acaba de llegar a una fiesta. Sintiéndose un poco tímido, se pregunta para sus adentros si conocerá a alguno de los invitados a la fiesta. Su anfitrión le dice "usted seguramente conoce a Rita, la mujer que se encuentra en la esquina cerca de la bandeja de quesos". En una fracción de segundo usted es capaz de echarle una mirada a Rita y verificar si realmente su anfitrión está en lo correcto o no. Sin embargo, en ausencia de esta sugerencia de su anfitrión, usted estaría obligado a realizar una revisión exhaustiva por todo el salón, chequeando las personas de la fiesta una por una, para ver si entre ellas hay alguna conocida.
Este es un ejemplo de un fenómeno general según el cual, en la mayoría de los problemas de decisión, generar una solución es mucho más difícil que comprobar que una solución específica es correcta. Por ejemplo, si alguien nos dice que el número 13.717.421 puede ser escrito como el producto de dos números menores, tal vez usted no sepa si creerle o no, pero si esta misma persona le dice que, en efecto, tal número se escribe como el producto de 3607 por 3803, entonces usted podrá comprobarlo muy fácilmente con la ayuda de una calculadora de bolsillo o manualmente.
Uno de los problemas más famosos en lógica matemática y en las ciencias de la computación es determinar si existen problemas de decisión que puedan ser resueltos por simples comprobaciones algorítmicas (por ejemplo, con la ayuda de una computadora) pero en cuyo proceso de solución se requiera de mucho más tiempo que lo usual. Pareciera que éste es el caso en una gran variedad de problemas de decisión bien estudiados, aunque hasta la fecha nadie ha podido demostrarlo formalmente.
Stephen Cook formuló este problema en 1971, que se le conoce como el Problema "P versus NP" y actualmente se le considera el problema central de las Ciencias de la Computación.
Este problema forma parte de los siete problemas del milenio, por los cuales el Instituto Clay ha ofrecido un millón de dólares por su solución.
Aunque es un problema que concierne sobre todo a las ciencias de la computación, su formulación se hace en el área de la lógica matemática, una de las áreas más abstractas de las matemáticas.

No hay comentarios: