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

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.