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 des 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].

Définitions[modifier | modifier le code]

On rappelle qu'un problème de décision peut être décrit par le langage des instances positives. On voit les instances comme des modèles. Un problème de décision est exprimable dans une certaine logique, s'il existe une formule de cette logique qui est satisfaite par un modèle si et seulement si ce modèle est une instance positive.

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, le langage est {G | 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 .

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

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 et les problèmes exprimables dans 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.

Exemple[modifier | modifier le code]

Graphe coloriable avec 3 couleurs.

Le problème de 3-coloration est décrit par le langage {G | il existe une 3-coloration des sommets de G telle deux sommets adjacentes ne soient pas de la même couleur}. Il est décrit par la formule de la logique du second ordre existentielle suivante : .

Par exemple, le graphe ci-contre est un modèle de cette formule car il est coloriable avec trois couleurs.

Résultats[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.

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]

La théorie de la complexité descriptive permet de montrer que les classes de complexité définies en utilisant les machines de Turing sont naturelles, dans le sens où elles apparaissent 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)
  • (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).