La teoría de la complejidad computacional es un área de la informática que estudia la complejidad intrínseca de los problemas. También se la conoce como clases de complejidad o teoría de la complejidad. La teoría examina tanto qué tan difícil es resolver un problema como qué tan eficientemente se puede resolver. Se centra en desarrollar una comprensión del costo de resolver problemas, qué problemas son difíciles de resolver y cómo se pueden desarrollar algoritmos eficientes para resolver esos problemas.
La teoría de la complejidad computacional está relacionada con la teoría de algoritmos y modelos computacionales. Se utiliza para clasificar problemas en términos de su dificultad y la cantidad de recursos computacionales necesarios para resolverlos. Generalmente, la complejidad de un problema se mide por la cantidad de tiempo y potencia informática que se necesita para resolverlo. Las clases de complejidad comunes incluyen NP-completo, P-completo, NP-duro y PSPACE-completo.
El concepto de teoría de la complejidad computacional se utiliza en diversas áreas, como la teoría de bases de datos, el análisis de big data, la criptografía, la inteligencia artificial y la computación cuántica. También es de gran importancia en el desarrollo de software informático, como juegos, gráficos por ordenador y aplicaciones comerciales.
Aunque la teoría es relativamente joven, ya que se propuso por primera vez en la década de 1970, ha experimentado un enorme crecimiento en los últimos años. Se ha convertido en una parte integral de la informática y sus aplicaciones en diversos campos. Como tal, es una herramienta esencial para los científicos e ingenieros informáticos que desean desarrollar algoritmos y software eficientes y eficaces para sus respectivos campos.
