Teoría de la complejidad computacional

¿Qué es la teoría de la complejidad y por qué ocupa un lugar tan central en la informática? La teoría de la complejidad estudia cuántos recursos - como tiempo de cálculo, memoria u otros - se requieren para resolver problemas algorítmicos. Permite comprender qué pueden hacer realmente los ordenadores y cuáles son los límites fundamentales de la computación, incluso cuando se dispone de los mejores algoritmos posibles. Desde las clases clásicas P y NP, pasando por las reducciones, la NP-completitud y los problemas de aproximación, hasta los sistemas de prueba interactivos, la teoría PCP y la complejidad de comunicación, este libro presenta de forma progresiva los conceptos esenciales del área. Lucien Sina no solo expone la teoría con rigor matemático, sino que también hace visibles las ideas e intuiciones que la sustentan. Numerosos ejemplos, demostraciones y ejercicios con soluciones facilitan la comprensión y permiten desarrollar una visión sólida de la eficiencia algorítmica. Este libro está dirigido a estudiantes de informática, docentes, investigadores y a todas las personas que buscan una introducción clara, rigurosa y bien estructurada a la teoría de la complejidad. Además, se integra en la serie de obras del autor - Algoritmos y estructuras de datos, Informática teórica, Lógica formal y Programación orientada a objetos en Java - , formando una colección coherente de estudio y consulta que abarca desde los fundamentos teóricos hasta la programación práctica. La teoría de la complejidad muestra hasta qué punto la teoría y la práctica de la informática están profundamente entrelazadas, y por qué conocer los límites de lo posible suele ser el primer paso para ampliarlos de manera creativa.