Complexité descriptive

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 :${\displaystyle \exists C_{1},\exists C_{2},\exists C_{3},\left(\forall s,\bigvee _{i=1}^{3}C_{i}(s)\right)\land \left(\forall s\bigwedge _{i,j=1i\neq j}^{3}(\lnot C_{i}(s)\lor \lnot C_{j}(s))\right)\land \left(\forall t,R(s,t)\rightarrow \bigwedge _{i=1}^{3}(\lnot C_{i}(s)\lor \lnot C_{i}(t))\right)}$. Cette formule se lit "il existe un ensemble de sommets C₁, un autre ensemble de sommets C₂, un autre ensemble de sommets C₃ (1, 2, 3 sont les trois couleurs possibles) tels que :
  • tout sommet est colorié (tout sommet est dans l'un des sous-ensemble C_i),
  • tout sommet n'a qu'une seule couleur au plus (tout sommet est dans au plus un des sous-ensemble C_i),
  • 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. Les instances positive d'un problème de décision (i.e. dans l'exemple les graphe 3-coloriable) sont exactement les modèles dans lesquelles la formule est vraie.

Considérons le problème de décision A qui consiste à déterminer si un graphe G est tel que tout sommet de G admet une arête incidente. Un graphe G est vu comme un modèle où les éléments du domaine sont les sommets du graphe et la relation du graphe est un prédicat ${\displaystyle R}$. Le problème de décision A est exprimable en logique du premier ordre car on décrit les instances positives par la formule ${\displaystyle \forall s,\exists t,sRt}$(tout sommet s admet un successeur t).

• (en) Ronald Fagin, « Generalized First-Order Spectra and Polynomial-Time Recognizable Sets », Proc. SIAM-AMS Sympos. Appl. Math., Amer. Math. Soc., vol. VII « Complexity of Computation »,‎ 1974, p. 43-73 (MR 0371622, lire en ligne, consulté le 7 novembre 2019)
• (en) Neil Immerman, « Languages Which Capture Complexity Classes », STOC '83 Proceedings of the fifteenth annual ACM symposium on Theory of computing,‎ 1983, p. 347-354 (ISBN 0-89791-099-0, DOI 10.1145/800061.808765, lire en ligne)
• (en) Serge Abiteboul et Victor Vianu, « Generic Computation and Its Complexity », STOC '91 Proceedings of the twenty-third annual ACM symposium on Theory of Computing,‎ 1991, p. 209-219 (ISBN 0-89791-397-3, DOI 10.1145/103418.103444)

• (en) Neil Immerman, Descriptive Complexity, New York, Springer-Verlag, 1999 (ISBN 0-387-98600-6, présentation en ligne)
• (en) Martin Grohe, Descriptive Complexity, Canonisation, and Definable Graph Structure Theory, Cambridge University Press, 2017, 554 p. (ISBN 978-1-139-02886-8, lire en ligne), chap. I.3 (« Descriptive complexity »), p. 40-93