The Golden Ticket: P, NP, and the Search for the Impossible de Lance Fortnow (Princeton University Press, 2013).
Escribir un libro sobre una de las grandes cuestiones de la humanidad de forma comprensible es todo un reto. Fortnow lo ha conseguido con creces, usando dos armas: por un lado la siempre elusiva brevedad y por otro la idea popularizada por Stephen Hawking de no incluir ni una sola ecuación en las páginas, so pena de perder con cada una de ellas la mitad de los lectores.
El problema P = NP es uno de los compejos más importantes de la teoría de la complejidad computacional. P y NP son los nombres con que se conocen a cierto tipo de problemas, de los cuales resulta relevante saber si pueden resolverse o no y con qué grado de eficacia. Hallar la ruta óptima para un viajante que debe recorrer muchas ciudades o cuál es el tamaño máximo de una pandilla de amigos que son amigos de sus amigos en Facebook son ejemplos de problemas NP. Encontrar un número en una hoja de cálculo, comprimir imágenes o jugar a las damas son de tipo P.
Se sabe que algunos problemas NP son equivalentes; resolverlos equivaldría a resolver todos ellos de golpe y supondría toda una revolución. Además de eso, quien lo haga ganará medallas y honores de todo tipo, un premio de un millón de dólares y seguramente una mención destacada en la Wikipedia. Pero aparte de esas minucias si P=NP estaríamos ante el fin de la criptografía convencional que se usa en Internet, los problemas de muchos problemas sin solución «por falta de potencia de cálculo» y pero veríamos increíbles avances en computación, adelantando dos o tres siglos de golpe la forma en que usamos los ordenadores y cómo ello afecta a nuestro mundo.
En el libro a lo largo de unos pocos cientos de página el autor examina con una brevedad increíble todas las cuestiones necesarias para comprender y maravillarse con la cuestión P = NP. Las fórmulas han sido reemplazadas por mapas, sudokus o cubos de Rubik... ¿hay algo más fácil? Lo mejor es que no hay que ser ningún experto para entender su profundidad, porque los ejemplos son especialmente fáciles de entender. Eso sí: cuanto más sepas sobre cuestiones matemáticas tales como complejidad, criptografía, teoría de grafos, teoría de números, algoritmos, topología y lógica mejor que mejor: más apreciarás cada una de sus sutilezas a su alrededor.
Algunos enlaces extra:
- The Status of the P Versus NP Problem en Communications of the ACM
- Gödel's Lost Letter and P=NP, un blog dedicado a la cuestión
- ¿P≠NP? un ejemplo de las innumerables «pruebas» de que P=NP o P≠NP que surgen cada semana de manos de aficionados y que llegan hasta las publicaciones especializadas: una pérdida de tiempo para todos
