Complexité descriptive

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

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[modifier | modifier le code]

Graphe coloriable avec 3 couleurs.

Exemple : coloriation d'un graphe[modifier | modifier le code]

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.

Problème de décision comme une requête[modifier | modifier le code]

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[modifier | modifier le code]

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 . Le problème de décision A est exprimable en logique du premier ordre car on décrit les instances positives par la formule (tout sommet s admet un successeur t).

Théorème de Fagin[modifier | modifier le code]

Article détaillé : 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[modifier | modifier le code]

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[modifier | modifier le code]

Intérêts[modifier | modifier le code]

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[modifier | modifier le code]

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

Bibliographie[modifier | modifier le code]

Articles[modifier | modifier le code]

  • (en) Ronald Fagin, « Generalized First-Order Spectra and Polynomial-Time Recognizable Sets », SIAM-AMS Proceedings, vol. 7 « Complexity of Computation »,‎ , p. 27-41 (lire en ligne, consulté le 1er juillet 2010)
  • (en) Neil Immerman, « Languages Which Capture Complexity Classes », 15th ACM STOC Symp.,‎ , p. 347-354 (lire en ligne)
  • (en) Serge Abiteboul et Victor Vianu, « Generic Computation and Its Complexity », STOC,‎ , p. 209-219

Ouvrages[modifier | modifier le code]

  • (en) Neil Immerman, Descriptive Complexity, New York, Springer-Verlag, (ISBN 0-387-98600-6, présentation en ligne)
  • (en) Martin Grohe, Descriptive Complexity, Canonisation, and Definable Graph Structure Theory (Preliminary version), (lire en ligne), chap. I.3 (« Descriptive complexity »)

Notes et références[modifier | modifier le code]

  1. a et b (Fagin 1974).
  2. a et b 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 2013)
  3. Cf. introduction de (Immerman 1983).
  4. (Abiteboul et Vianu 1991).