Lance Fortnow

Muy decepcionante. El libro parece tratar en principio sobre el problema de P y NP, pero lo que el autor tiene que contar sobre la materia es tan poco que hay decenas de páginas de relleno. Hay partes de relleno muy divertidas e interesantes, como la completísima historia de ficción en la que se demuestra que P=NP y por tanto todo problema computacional puede reducirse a otro problema resoluble en tiempo polinómico. El autor hace en esa historia un fantástico ejercicio de imaginación comparable, creo al de alguien a quien le pidieran en 1970 qué pasaría si todo el mundo tuviera a acceso a internet.
Pero luego nos llegan las disgresiones, la introducción a los algoritmos de cifrado(sin relacionarlos mucho con P=NP), la criptografía cuántica (para la que de momento no hay mucho armamento algorítmico puesto en producción)... y otras cosas que me hacen echar de menos el tema principal del libro. Un poco disperso, vaya. Lo que cuenta es interesante pero yo esperaba algo más técnico y más centrado en el tema principal.… (más)

The famous unsolved "P=NP?" theoretical problem in computer science (and mathematics) basically asks whether every computational problem whose solutions can be quickly checked also has the property that the solutions can be quickly generated in the first place. Though believed and assumed to be false, no disproof (or awarding of the million-dollar prize therefor) is in sight. Fortnow offers a (perhaps too) informal and pretty short exposition of the problem, its importance, related topics, and practical implications. An appendix, not included, could have explained that the technical criterion for problem-solving tractability is running time proportional to some polynomial function (not exponential or factorial) of the size of the input data.… (más)

A rare popular science book about the P vs NP problem. The author takes care in using concrete examples and simplifying explanations as much as possible, though I think at times he makes it too simple. I especially liked that he included the history of how the problem developed on both sides of the iron curtain during the cold war. This book may be a nice read for people who don't have much of a science or math background, but for those who do I don't think they will get enough out of it compared with just reading some wikipedia articles.… (más)