La teoría de la complejidad computacional es un área de las matemáticas y la informática que se ocupa de los recursos necesarios para resolver problemas en un sistema informático. Hay varias técnicas disponibles para determinar los requisitos de recursos de un problema. Es posible que algunos problemas no sean factibles en los sistemas informáticos existentes debido a la demanda de recursos. Los investigadores clasifican los problemas por dificultad y pueden dividir los cálculos en problemas polinomiales (P) versus polinomiales no terministas (NP).
Resolver un cálculo requiere recursos como tiempo, espacio de almacenamiento y hardware. Un sistema informático puede tener limitaciones que hacen que un problema sea funcionalmente imposible de resolver porque no tiene los recursos disponibles. A medida que mejora la tecnología informática, un problema que antes no tenía solución podría volverse solucionable con la ayuda de nuevas tecnologías e investigaciones en el campo de la teoría de la complejidad computacional. La capacidad de solución de un problema no está necesariamente determinada por su complejidad, sino por los algoritmos utilizados para resolverlo.
En la teoría de la complejidad computacional, un problema P es uno que se puede resolver en tiempo polinomial con un algoritmo sencillo. Es posible que aún requiera recursos sustanciales, pero se puede resolver y verificar por computadora. Se podría pensar que tales problemas se pueden resolver rápidamente siempre que una computadora tenga los recursos disponibles para manejar los cálculos necesarios.
Los problemas de NP son más complejos. No es posible aplicar un solo algoritmo y podría ser necesario utilizar opciones más avanzadas, como máquinas de Turing paralelas que pueden explorar varias opciones. El problema podría resolverse de esta manera, pero requerirá sustancialmente más recursos. Estos problemas podrían ser más fáciles para los operadores humanos que son capaces de un pensamiento lógico avanzado, porque el punto de inflexión es a menudo uno de lógica en lugar de una dificultad de cálculo pura. El problema del viajante de comercio, en el que el objetivo es encontrar la ruta más eficiente entre varias ciudades a lo largo de una ruta, es un ejemplo clásico de un problema NP en la teoría de la complejidad computacional.
La clasificación de problemas P versus NP a través de la teoría de la complejidad computacional puede ser una tarea compleja y los problemas pueden cambiar de un lado a otro a través de la división. Un pequeño conjunto de problemas computacionales no encaja perfectamente en ninguna de las categorías y, a veces, se clasifican como ninguno para reflejar esto. Eventualmente, podría ser posible desarrollar un algoritmo para resolver un problema de NP y, en algunos casos, podría aplicarse a otros problemas que tienen una estructura similar. En otros, sin embargo, puede ser un problema específico. El proceso de explorar dichos programas y desarrollar enfoques para resolverlos es un área importante de las matemáticas y la informática que contribuye al desarrollo de sistemas informáticos avanzados y de gran potencia.