Êtes-vous un étudiant de l'EPFL à la recherche d'un projet de semestre?
Travaillez avec nous sur des projets en science des données et en visualisation, et déployez votre projet sous forme d'application sur Graph Search.
Concept
Complexité descriptive
Résumé
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.
vignette|Graphe coloriable avec 3 couleurs.
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.
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.
Source officielle
À propos de ce résultat
Cette page est générée automatiquement et peut contenir des informations qui ne sont pas correctes, complètes, à jour ou pertinentes par rapport à votre recherche. Il en va de même pour toutes les autres pages de ce site. Veillez à vérifier les informations auprès des sources officielles de l'EPFL.