Hiérarchie booléenne

En informatique théorique, plus précisément en théorie de la complexité, la hiérarchie booléenne (notée BH pour Boolean hierarchy en anglais) est une hiérarchie de classes de complexité obtenues comme combinaisons booléennes (intersections, unions, et passage au complémentaire) de problèmes de décision de NP[1]. Plus précisément, un langage/problème de décision dans la hiérarchie booléenne s'écrit comme une « formule booléenne » où les « variables » sont des langages de NP, par exemple ${\overline {(L_{1}\cap L_{2})\cup L_{3}}}$ appartient à la hiérarchie booléenne si $L_{1}$ , $L_{2}$ , $L_{3}$ sont des langages de NP.

Définition formelle

On définit BH_i par récurrence sur i :

BH₁ = NP ;
BH_2k est la classe des langages qui peuvent être décrits par l'intersection d'un langage de BH_2k-1 et d'un langage de co-NP ;
BH_2k+1 est la classe des langages qui peuvent être décrits par l'union d'un langage de BH_2k et d'un langage de NP.

BH est l'union des BH_i.

BH₂ est noté DP (Difference Polynomial Time)[2].

Propriétés

Si la hiérarchie booléenne s'effondre, alors la hiérarchie polynomiale s'effondre à Σ₃P[3] - [4]. Elle est incluse dans Δ₂P.

Exemples de problèmes

Le problème MAX-CLIQUE, étant donné un graphe non orienté G et un entier k, savoir si une clique maximale de G est de taille k, est DP-complet[2].

Notes et références

(en) Gerd Wechsung, « On the boolean closure of NP », Fundamentals of Computation Theory, Springer, Berlin, Heidelberg, lecture Notes in Computer Science,‎ 9 septembre 1985, p. 485–493 (ISBN 9783540156895, DOI 10.1007/BFb0028832, lire en ligne, consulté le 29 septembre 2017)
(en) Sipser, Introduction to the Theory of Computation
R. Chang et J. Kadin, « The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection », SIAM Journal on Computing, vol. 25,‎ 1^er avril 1996, p. 340–354 (ISSN 0097-5397, DOI 10.1137/S0097539790178069, lire en ligne, consulté le 22 août 2016)
(en) « Complexity Zoo:B - Complexity Zoo », sur complexityzoo.uwaterloo.ca (consulté le 29 septembre 2017)

Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.