Complexité descriptive

En informatique théorique, la complexité descriptive est une branche de la théorie de la complexité et de la théorie des modèles, qui caractérise les classes de complexité en termes de logique qui permet de décrire les problèmes. La complexité descriptive donne un nouveau point de vue car on définit des classes de complexité sans faire appel à une notion de machines comme les machines de Turing. Par exemple la classe NP correspond à l'ensemble des problèmes exprimables en logique du second ordre existentielle : c'est le théorème de Fagin. vignette|Graphe coloriable avec 3 couleurs. Expliquons le principe de la complexité descriptive avec le problème de 3-coloration d'un graphe. Il s'agit du problème de décision qui consiste à savoir, étant donné un graphe, si on peut colorier ses sommets avec trois couleurs de façon que deux sommets adjacents ne soient pas de la même couleur. La figure à droite donne un exemple d'un graphe 3-coloriable. Le problème de 3-coloration est dans la classe NP. En effet, étant donné un coloriage, il est facile de vérifier (i.e. en temps polynomial en la taille du graphe) que deux sommets adjacents ne sont pas de la même couleur. D'autre part, le problème de 3-coloration est décrit par la formule de la logique du second ordre existentielle suivante :. Cette formule se lit "il existe un ensemble de sommets C1, un autre ensemble de sommets C2, un autre ensemble de sommets C3 (1, 2, 3 sont les trois couleurs possibles) tels que : tout sommet est colorié (tout sommet est dans l'un des sous-ensemble Ci), tout sommet n'a qu'une seule couleur au plus (tout sommet est dans au plus un des sous-ensemble Ci), deux sommets adjacents sont de couleurs différentes. Ainsi, en complexité descriptive, un problème de décision est décrit par une formule logique, qui correspond à faire une requête (par exemple, la requête "est-ce que le graphe est 3-coloriable ?"). Une instance d'un problème de décision est un modèle (par exemple, un graphe pour le problème de 3-coloration est vu comme un modèle) sur lequel on peut évaluer des formules logiques.