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^[1],[2].

Principe

Graphe coloriable avec 3 couleurs.

Exemple : coloration d'un graphe

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.

Problème de décision comme une requête

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.

Autre exemple

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).

Théorème de Fagin

Le premier résultat du domaine, et l'un des plus importants est le théorème de Fagin^[1],[2] qui donne l'équivalence entre :

• la classe NP, par définition, la classe des problèmes de décision pour lesquels il est facile de vérifier l'existence d'une solution ;
• et la classe des problèmes exprimables en la logique du second ordre existentielle, c'est-à-dire la logique du second ordre où on interdit de quantifier universellement sur les prédicats et fonctions.

Correspondance entre classes et logiques

De nombreuses autres classes ont aussi été caractérisées de la même manière et sont résumés dans la table suivante, pour la plupart par Neil Immerman.

Classes de complexité	Logiques correspondantes
AC⁰	logique du premier ordre
NL	logique du premier ordre avec une clôture transitive
P	logique du premier ordre avec plus petit point fixe
NP	logique du second ordre existentielle
co-NP	logique du second ordre universelle
PH	logique du second ordre
PSPACE	logique du second ordre avec une clôture transitive
EXPTIME	logique du second ordre avec plus petit point fixe
ELEMENTARY	logique d'ordre supérieur
RE	logique du premier ordre existentielle sur les entiers
co-RE	logique du premier ordre universelle sur les entiers

Exemple pour NL

Intérêts

Neil Immerman justifie la théorie de la complexité descriptive car elle montre que les classes de complexité définies en utilisant les machines de Turing sont naturelles : elles sont définissables même si on n'utilise pas les modèles de calculs classiques^[3]. De plus cette théorie donne un nouveau point de vue sur certains résultats et certaines conjecture de théorie de la complexité, par exemple le théorème d'Abiteboul et Vianu (en)^[4] indique que les classes P et PSPACE sont égales si les logiques Inflationary Fix Point (IFP) et Partial Fix Point (PFP) sont égales.

Lien externe

Page de Neil Immerman sur la complexité descriptive, avec un diagramme.

Variantes

La classe PTIME intersectée avec des problèmes invariants par bisimulation correspond à la logique du mu-calcul de dimension supérieure^[5].

Bibliographie

Articles

• (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)

Ouvrages

• (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

Notes et références

1. (Fagin 1974).
2. Sources pour l'importance : We are now ready to state Fagin's Theorem and the Immerman-Vardi Theorem, arguably the two most fundamental results in descriptive complexity theory. dans (Grohe 2017)
3. Cf. introduction de (Immerman 1983).
4. (Abiteboul et Vianu 1991).
5. Martin Otto, « Bisimulation-invariant PTIME and higher-dimensional μ-calculus », Theoretical Computer Science, vol. 224, n^o 1,‎ 6 août 1999, p. 237–265 (ISSN 0304-3975, DOI 10.1016/S0304-3975(98)00314-4, lire en ligne, consulté le 22 novembre 2019)

• Portail de l'informatique théorique