P versus NP, he ahí el dilema
El problema más famoso en ciencias de la computación, sobre cuya cabeza pesa una recompensa de un millón de dólares, nació como un enigma matemático más. Atractivo e interesante, sin duda, pero humilde. Ni siquiera su descubridor, el matemático estadounidense Stephen Cook, advirtió al principio sus muchas implicaciones.
Se trata del problema P versus NP, que se ocupa de lo que puede resolver una computadora de forma eficiente. Cook lo formuló en 1971. La era de los ordenadores estaba entonces en sus inicios y el valor de la aportación de Cook no era fácilmente apreciable.
Sin embargo, solo un año después otro matemático publicó una lista con decenas de problemas que en la práctica, y según el estado de conocimiento actual, quedan fuera del alcance de las computadoras. Eran muchos más de los esperados. Fue el comienzo de la fama de P versus NP, y de Stephen Cook.
Con los años la lista de problemas irresolubles en tiempo asumible ha seguido creciendo y P versus NP se ha convertido en una espada Excálibur a la que todo genio matemático se ha enfrentado alguna vez. En cuanto a Stephen A. Cook (Búfalo, Estados Unidos,1939), hoy es catedrático de Ciencias de la Computaciónen la Universidad de Toronto y el ganador del Premio Fundación BBVA Fronteras del Conocimiento en la categoría de Tecnologías de la Información y la Comunicación «por su trabajo pionero de enorme influencia en complejidad computacional».
Stephen Cook. ©NSERC
De niño Cook no conocía a ningún matemático, no sabía «lo que hacían realmente» —ha comentado en alguna ocasión—, pero en cambio sí tenía la experiencia de haber trabajado un verano siendo adolescente con el inventor del marcapasos cardiaco implantable, Wilson Greatbach, quien vivía en su misma ciudad. Eso, unido a su interés por los transistores que empezaban a llegar al mercado, le hizo matricularse en Ingeniería en la Universidad de Míchigan.
Un profesor que advirtió sus habilidades le ganó para las matemáticas. Tras doctorarse en Harvard en 1966, comenzó su relación con las ciencias de la computación, un área que los matemáticos, en palabras del propio Cook, «aún no consideraban del todo respetable matemáticamente».
Quizás por eso el Departamento de Matemáticas de la Universidad de California en Berkeley, donde Cook fue profesor cuatro años, no le ofreció un puesto estable. Richard Karp, del Departamento de Ciencias de la Computación en Berkeley, ha escrito: «Será siempre motivo de vergüenza para nosotros el no haber logrado convencer al Departamento de Matemáticas [de ofrecer una plaza a Cook]». En 1970 Cook aceptó una oferta de la Universidad de Toronto.
Detalle de la máquina Bombe, creada por el matemático británico Alan Turing para decodificar los mensajes cifrados del ejército alemán durante la Segunda Guerra Mundial.
En esa época «los ordenadores eran relativamente nuevos y parecía muy natural estudiar qué problemas pueden resolver de forma eficiente», dice Cook para explicar por qué escogió su área de investigación. La cuestión de la eficiencia es importante. Alan Turing ya había definido décadas atrás qué pueden resolver los ordenadores y qué no en términos absolutos. Pero sucede que «hay problemas que sí pueden ser resueltos por un ordenador, solo que la máquina tardaría tanto que el Sol moriría antes», señala Cook.
Estos problemas en la práctica irresolubles se dan en biología, física, economía… y es interesante identificarlos para no «desperdiciar esfuerzo» intentando resolverlos y concentrarse, en cambio, en la búsqueda de «soluciones aproximadas pero útiles», señala Cook.
Lo que más me gusta de las matemáticas es la idea de que puedes demostrar que una determinada proposición es cierta y no existe argumento racional que lo ponga en duda — Cook
Hoy día no cabe ya duda de la admiración que matemáticos y expertos en computación sienten por el padre de P versus NP, uno de los siete problemas del milenio, cuya resolución premia con un millón de dólares el Clay Mathematics Institute (Estados Unidos).
NP —por sus siglas en inglés de tiempo no determinista polinomial— son los problemas que no pueden ser resueltos eficientemente, y P los que sí. Un ejemplo de problema NP es el conocido como del viajante: se trata de hallar la ruta más corta para un repartidor que debe entregar muchos paquetes. En los problemas NP solo se encuentra la respuesta correcta probando todas las opciones, algo que puede llevar miles de millones de años incluso al ordenador más potente.
Mapa de las rutas aéreas mundiales / Jpatokal (Wikipedia Commons)
Ahora bien, ¿seguro que no existe un algoritmo que dé una solución evitando hacer todos esos cálculos? ¿De verdad no hay un atajo brillante para resolver los problemas NP? Justamente eso es lo que plantea el problema P versus NP. A fecha de hoy, la respuesta es un rotundo «no se sabe». Es posible que los NP sean, en realidad, problemas P disfrazados, problemas solubles eficientemente pero para los que nadie ha encontrado todavía el método de ataque adecuado.
La gran aportación de Cook fue determinar que dentro de la clase NP hay una subclase que denominó NP completa. Los NP completos son problemas llave, porque si se encuentra una manera de resolver eficientemente solo uno de ellos, significa que todos —todos los NP— pueden resolverse eficientemente. A la inversa, si se demostrara que realmente no existe método capaz de resolver un NP completo en tiempo asumible, la barrera entre P y NP quedaría blindada para siempre.
Cook apuesta por la última opción. Esa es su conjetura: que P y NP son distintos. A él lo que más le gusta de las matemáticas es «la idea de que puedes probar que una proposición precisa es verdadera sin que ningún argumento racional pueda poner en duda ese hecho». Pero no le queda más remedio, por ahora, que aceptar que la conjetura de Cook viva en el limbo de lo que todavía no ha podido ser demostrado.