Ê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
Hiérarchie polynomiale
Résumé
En théorie de la complexité, la hiérarchie polynomiale est une hiérarchie de classes de complexité qui étend la notion de classes P, NP, co-NP. La classe PH est l'union de toutes les classes de la hiérarchie polynomiale.
Il existe plusieurs définitions équivalentes des classes de la hiérarchie polynomiale.
On peut définir la hiérarchie à l'aide des quantificateurs universel () et existentiel (). Tout d'abord, pour tout polynôme , et tout langage , on définit
c'est-à-dire que l'ensemble contient exactement l'ensemble des mots pour lesquels il existe un mot de taille polynomiale en la longueur de x tel que le mot est dans . Intuitivement, le mot joue le rôle d'un certificat pour , certificat relativement petit par rapport à . De la même façon on définit
On étend ces définitions aux classes de langages
Maintenant, on peut définir les classes de la hiérarchie polynomiale par récurrence de la façon suivante :
En particulier, et .
La hiérarchie polynomiale est également définissable à l'aide de machine de Turing avec oracle. dénote la classe des problèmes pouvant être décidés par des machines de complexité augmentées d'un oracle de complexité .
On pose
Puis pour tout i ≥ 0 :
La hiérarchie polynomiale peut se définir à l'aide de machines de Turing alternantes. est la classe des langages décidés par une machine de Turing alternante en temps polynomial, dans laquelle toute exécution est composée de i suites de configurations de même type (existentielles ou universelles), la première suite ne contenant que des configurations existentielles. La définition de est similaire mais les configurations dans la première suite sont universelles.
Savoir si une formule de la logique propositionnelle est minimale, c'est-à-dire s'il n'existe pas de formules plus courtes équivalentes, est un problème algorithmique dans .
Une autre propriété importante, interne à la hiérarchie polynomiale, est la suivante : , ce qui signifie que si à un niveau deux classes sont égales, alors toutes les classes « au-dessus » sont égales.
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.