Hiérarchie booléenne
# 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. 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_1$ = 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_2$ est noté DP (Difference Polynomial Time).

## Propriétés

Si la hiérarchie booléenne s'effondre, alors la hiérarchie polynomiale s'effondre à $Σ_3P^,.$ Elle est incluse dans $Δ_2P.$

## 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.

