La teoría de la complejidad computacional[1]​ o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad. Wikipedia

Rama de la teoría de la computación, que investiga los problemas relacionados con las cantidades de recursos requeridos para la ejecución de algoritmos (por ejemplo, en tiempo de ejecución), y la dificultad inherente para producir algoritmos eficientes para resolver problemas de cómputo específicos. OmegaWiki

Problema que puede ser resuelto, pero no lo suficientemente rápido como para que su solución sea útil. OmegaWiki