Aparentemente la más importante pregunta en ciencias de la computación ha sido resuelta por Vinay Deolalikar, un matemático de Hewlett-Packard. Su respuesta es: P ≠ NP. Y de ser así se ha hecho acreedor a un premio de 1 millón de dólares.
La pregunta P versus NP está relacionada directamente con la velocidad en la cual una computadora puede realizar una tarea tal como factorización de un número. Algunas tareas pueden completarse con razonable facilidad -en términos técnicos, el tiempo de ejecución es proporcional a la función de polinomio de su tamaño de entrada- y estas tareas están en la clase P. Si la respuesta para una tarea es que puede ser completada fácilmente, entonces se encuentra en la clase NP. De tal manera que si P = NP eso significa que todo problema que puede revisarse fácilmente puede también ser completado fácilmente.
Pero si Deolalikar está en lo correcto, esto probaría que las dos clases P y NP no son idénticas, y eso impone serios límites a lo que las computadoras pueden lograr -implicando que algunas tareas serán de manera irreductible muy complejas para realizarse.
Deolalikar indica que no hay forma de que así sea. Su argumento se basa en una tarea especifica, el problema de satisfaccibilidad Booleana, que consiste en si un grupo de declaraciones lógicas pueden ser simultáneamente ciertas o si se contradicen entre ellas. Este se conoce como un problema NP.
Deolalikar dice que él ha demostrado que no existe un programa que pueda completar esto fácilmente desde cero, y que por consiguiente no existe problema P. Su argumento incluye el uso brillante de la física estadística al mismo tiempo que utiliza una estructura matemática que sigue muchas de las reglas de un sistema físico aleatorio.
Los teóricos de la Complejidad le han dado al ensayo de Deolalikar una recepción favorable, y será cuando la versión final sea liberada en aproximadamente una semana que el proceso de revisión se hará mucho más intenso.
Puedes leer el artículo completo en inglés aquí.
Comentarios