P, Np y Np-Completitud: Los fundamentos de la complejidad computacional

Opiniones de los lectores

Las críticas destacan «El billete dorado» de Fortnow como una valiosa introducción al problema P contra NP, que equilibra la accesibilidad con la profundidad. Muchos lectores aprecian el atractivo estilo de redacción, las anécdotas y la claridad de las explicaciones, que hacen que los temas complejos resulten accesibles para los profanos. Sin embargo, algunos lectores tienen problemas con las notaciones técnicas y les resulta difícil seguirlas, lo que sugiere la necesidad de conocimientos previos o de una comprensión básica.

⬤ Estilo de redacción ameno y legible
⬤ explicaciones claras de temas complejos
⬤ incluye anécdotas y diagramas
⬤ amplia cobertura de P vs NP y temas relacionados
⬤ considerado una introducción suave a un tema difícil.

⬤ Utiliza notaciones no explicadas, lo que dificulta su comprensión a algunos lectores
⬤ requiere conocimientos previos para su plena comprensión
⬤ puede ser demasiado simplista para lectores avanzados.

(basado en 2 opiniones de lectores)

Título original:

P, Np, and Np-Completeness: The Basics of Computational Complexity

Contenido del libro:

Este libro se centra en la cuestión P-versus-NP y en la teoría de la completitud NP. También proporciona los preliminares adecuados en relación con los problemas computacionales y los modelos computacionales.

La pregunta P-versus-NP plantea si encontrar soluciones es más difícil que comprobar la corrección de las soluciones. Una formulación alternativa pregunta si descubrir pruebas es más difícil que verificar su corrección. Existe la creencia generalizada de que la respuesta a estas formulaciones equivalentes es positiva, y esto se capta diciendo que P es diferente de NP.

Aunque la cuestión P-versus-NP sigue sin resolverse, la teoría de la NP-completitud ofrece pruebas de la intratabilidad de problemas específicos en NP al mostrar que son universales para toda la clase. Sorprendentemente, existen problemas NP-completos y, además, cientos de problemas computacionales naturales que surgen en muchas áreas diferentes de las matemáticas y la ciencia son NP-completos.