Jerarquia booleana

En teoria de la complexitat, la jerarquia booleana (també coneguda per BH, de Boolean Hierarchy) és la jerarquia de combinacions booleanes (intersecció, unió i complementació) dels conjunts NP. També es pot descriure com la classe de circuits booleans sobre predicats NP. El col·lapse de la jerarquia booleana implicaria un col·lapse de la jerarquia polinòmica.

Definició

La jerarquia booleana (BH) es pot definir com:

• BH_{1 és NP-}
• BH_2k és la classe de llenguatges que son la intersecció d'un llenguatge a BH_2k-1 i un llenguatge a coNP.
• BH_2k+1 és la classe de llenguatges que son la unió d'un llenguatge a BH_2k i un llenguatge a NP.
• BH és la unió de tots els BH_i.

També es pot definir de la següent manera. Primer cal definir la conjunció i la disjunció de la següent forma:

$C\wedge D=A\cap B|A\in C,B\in D$

$C\vee D=A\cup B|A\in C,B\in D$

Que vol dir que la conjunció de dues classes conté els llenguatges que son la intersecció d'un llenguatge de la primera classe i un llenguatge de la segona classe. La disjunció es defineix d'una forma equivalent.

Segons aquesta definició, DP = NP ∧ coNP.

Les altres classes de la jerarquia booleana es poden definir així:

$B{H}_{2k}=coNP\wedge B{H}_{2k-1}$

$B{H}_{2k+1}=NP\vee B{H}_{2k}$

Que també es poden definir de la següent manera:

$B{H}_{2k}=\underset{i=1}{\overset{k}{\bigvee }}DP$

$B{H}_{2k+1}=NP\vee \underset{i=1}{\overset{k}{\bigvee }}DP$

O alternativament, per tot k ≥ 3:

$B{H}_k=DP\vee B{H}_{k-2}$

Relacions entre classes de la jerarquia polinòmica

La classe DP (Difference Polynomial Time) és equivalent a BH₂.