Théories de la complexités (informatiques théoriques), domaine des mathématiques, de l'informatique théorique, l'espace mémoire (taille d'un circuit, le nombre de processeurs, l'énergie consommée.
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é. Problèmes de décision posent une question dont la réponse est oui ou non. Problèmes d'optimisations peuvent se formaliser sous la forme de la maximisation. Passage de problème d'optimisation à problème de décision.
Complexité existent :
- Machines de Turing non-déterministes,
- Machines de Turing alternantes,
- Machines de Turing probabilistes,
- Machine RAM (Random Access Machine),
- Circuits booléens et les programmes straight-line,
- Fonctions récursives, dues à Kleene,
- Lambda-calcul,
- Automates cellulaires,
- Logique linéaire,
- Pebble games.
D'autre mesures existent :
- Nombre de communications (voir la théorie de la complexité de la communication),
- Nombre de portes dans un circuit booléen,
- Profondeur d'un circuit booléen,
- Nombre d'alternations (voir machines alternantes).
