Complexité descriptive
# 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^,.$

## Principe

### 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 :$\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_1,$ un autre ensemble de sommets $C_2,$ un autre ensemble de sommets $C_3$ (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 $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 $\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^,$ 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 |

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

