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.^[1]

Definició

La jerarquia booleana (BH) es pot definir com:^[2]

• 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:

${\displaystyle C\land D={A\cap B|A\in C,B\in D}}$

${\displaystyle C\lor 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í:

${\displaystyle BH_{2k}=coNP\land BH_{2k-1}}$

${\displaystyle BH_{2k+1}=NP\lor BH_{2k}}$

Que també es poden definir de la següent manera:^[3]

${\displaystyle BH_{2k}=\bigvee _{i=1}^{k}DP}$

${\displaystyle BH_{2k+1}=NP\lor \bigvee _{i=1}^{k}DP}$

O alternativament, per tot k ≥ 3:^[4]

${\displaystyle BH_{k}=DP\lor BH_{k-2}}$

Relacions entre classes de la jerarquia polinòmica

La classe DP (Difference Polynomial Time) és equivalent a BH₂.^[5]

Referències