Théorie de la complexité (informatique théorique)

vignette|Quelques classes de complexité étudiées dans le domaine de la théorie de la complexité. Par exemple, P est la classe des problèmes décidés en temps polynomial par une machine de Turing déterministe. La théorie de la complexité est le domaine des mathématiques, et plus précisément de l'informatique théorique, qui étudie formellement le temps de calcul, l'espace mémoire (et plus marginalement la taille d'un circuit, le nombre de processeurs, l'énergie consommée ...) requis par un algorithme pour résoudre un problème algorithmique. Il s'agit donc d'étudier la difficulté intrinsèque des problèmes, de les organiser par classes de complexité et d'étudier les relations entre les classes de complexité. vignette|Le problème de voyageur de commerce : calculer un plus court circuit qui passe une et une seule fois par toutes les villes (ici 15 villes). Considérons l'exemple du problème du voyageur de commerce. La donnée du problème est un ensemble de villes et de distances séparant ces villes. L'objectif du problème est de trouver un plus court circuit qui passe une et une seule fois par toutes les villes. Il existe un problème de décision associé : étant donné un ensemble de villes, les distances entre villes et un entier k, déterminer s'il existe un circuit qui passe une et une seule fois par toutes les villes de longueur inférieure à k. Ainsi, on distingue deux types de problèmes. Les problèmes de décision posent une question dont la réponse est oui ou non ; dans le cas du problème du voyageur de commerce : existe-il oui ou non un circuit de longueur inférieure à k ? Les problèmes de recherche d'une solution comportent une question ou plutôt une injonction de la forme « renvoyer un élément tel que... » dont la réponse consiste à fournir un tel élément; dans le cas du problème du voyageur de commerce, exhiber un circuit de longueur minimale. Il s'agit donc d'un problème fonctionnel, et il sera donc catégorisé dans une classe fonctionnelle, par exemple FP si la solution est calculée en temps polynomial.