La
théorie de la complexité est un domaine des
mathématiques, et plus précisément de l'
informatique théorique, qui étudie formellement la
quantité de ressources (en temps et en espace) nécessaire pour la résolution
de problèmes au moyen de l'exécution d'un
algorithme. Il s'agit donc d'étudier la difficulté intrinsèque de problèmes posés mathématiquement.