Die Boolesche Hierarchie ist eine Hierarchie von Komplexitatsklassen , die als boolesche Kombinationen von NP -Problemen gebildet werden.

Zunachst definieren wir boolesche Konnektive fur Komplexitatsklassen. Seien ${\displaystyle {\mathcal {C}},{\mathcal {C'}}}$ zwei Komplexitatsklassen, dann

• ${\displaystyle {\mathcal {C}}\wedge {\mathcal {C'}}=\{L_{1}\cap L_{2}\mid L_{1}\in {\mathcal {C}},L_{2}\in {\mathcal {C'}}\}}$
• ${\displaystyle {\mathcal {C}}\vee {\mathcal {C'}}=\{L_{1}\cup L_{2}\mid L_{1}\in {\mathcal {C}},L_{2}\in {\mathcal {C'}}\}}$
• ${\displaystyle co{\mathcal {C}}=\{L\mid {\bar {L}}\in {\mathcal {C}}\}}$, wobei ${\displaystyle {\bar {L}}}$ das Komplement von ${\displaystyle {L}}$ ist.

Ausgehend von NP konnen die verschiedenen Ebenen der Booleschen Hierarchie (BH) definiert werden:

• ${\displaystyle BH_{1}=NP}$
• ${\displaystyle BH_{2k}=coNP\wedge BH_{2k-1}}$
• ${\displaystyle BH_{2k+1}=NP\vee BH_{2k}}$

Zum Beispiel ${\displaystyle BH_{2}=coNP\wedge NP}$ und ${\displaystyle BH_{3}=NP\vee (coNP\wedge NP)}$.

Die Boolesche Hierarchie (BH) wird dann als die Vereinigung aller ihrer Level definiert, also ${\displaystyle BH=\bigcup _{i\geq 1}BH_{i}}$.

Die Boolesche Hierarchie kann fur ${\displaystyle k\geq 1}$ auch wie folgt charakterisiert werden ^[1] :

• ${\displaystyle BH_{2k}=\bigvee _{i=1}^{k}(NP\land coNP)}$
• ${\displaystyle BH_{2k+1}=NP\vee \bigvee _{i=1}^{k}(NP\land coNP)}$

Seien ${\displaystyle {\mathcal {C}},{\mathcal {C'}}}$ zwei Komplexitatsklassen, dann ist

• ${\displaystyle {\mathcal {C}}\oplus {\mathcal {C'}}=\{L_{1}\bigtriangleup L_{2}\mid L_{1}\in {\mathcal {C}},L_{2}\in {\mathcal {C'}}\}}$, wobei ${\displaystyle \bigtriangleup }$ die symmetrische Differenz darstellt.

Dann lasst sich ${\displaystyle BH_{k}}$ als ${\displaystyle BH_{k}=BH_{k-1}\oplus NP}$ bzw. ${\displaystyle BH_{k}=\bigoplus _{i=1}^{k}NP}$ charakterisieren. ^[1]

Ausgehend von einem beliegen NP-vollstandigen Problem A (z. B.: SAT ) kann man eine Familie von vollstandigen Problemen fur verschiedene Level der Booleschen Hierarchie wie folgt definieren ^[2] .

Gegeben sei eine Folgen ${\displaystyle x_{1},\dots x_{m}}$ von verschiedenen Instanzen des Problems A, sodass wann immer ${\displaystyle x_{i}\in A}$ gilt, auch ${\displaystyle x_{i-1}\in A}$ gilt.

• Zu entscheiden, ob in einer Folge der Lange ${\displaystyle 2k}$ eine ungerade Anzahl an Instanzen in A sind, ist ${\displaystyle BH_{2k}}$-vollstandig.
• Zu entscheiden, ob in einer Folge der Lange ${\displaystyle 2k+1}$ eine gerade Anzahl an Instanzen in A sind, ist ${\displaystyle BH_{2k+1}}$-vollstandig.

• Sollte die Boolesche Hierarchie kollabieren, dann kollabiert auch die polynomielle Hierarchie zu ${\displaystyle \Sigma _{3}^{\rm {P}}}$.
• ${\displaystyle BH\subseteq \Delta _{2}^{\rm {P}}}$
• ${\displaystyle NP\subseteq BH}$ und ${\displaystyle coNP\subseteq BH}$

Die Klasse DP (Difference Polynomial Time) wurde von Papadimitriou and Yannakakis eingefuhrt ^[3] und ist wie folgt definiert. Eine Sprache ${\displaystyle L}$ ist in DP genau dann, wenn es Sprachen ${\displaystyle \textstyle L_{1}\in NP,L_{2}\in coNP}$ gibt, so dass ${\displaystyle L=L_{1}\cap L_{2}}$.

Damit entspricht DP dem zweiten Level ${\displaystyle BH_{2}}$ der Booleschen Hierarchie.

Das SAT-UNSAT-Problem ist das kanonische vollstandige Problem fur die Klasse DP.

Eine SAT-UNSAT-Instanz besteht aus einem Paar ${\displaystyle (\phi ,\psi )}$ von aussagenlogischen Formeln (wahlweise in 3- KNF ). Die Problemstellung ist zu entscheiden, ob ${\displaystyle \phi }$ erfullbar (SAT) und ${\displaystyle \psi }$ unerfullbar (UNSAT) ist.

Die vollstandigen Probleme der Klasse DP konnen auch wie folgt charakterisiert werden ^[4] .

Eine Sprache L ist DP-vollstandig genau dann, wenn alle der folgenden Bedingungen erfullt sind:

1. ${\displaystyle L\in DP}$
2. ${\displaystyle L}$ ist NP-schwer
3. ${\displaystyle L}$ ist coNP-schwer
4. ${\displaystyle L}$ hat die ${\displaystyle AND_{2}}$-Eigenschaft: Die Sprache ${\displaystyle AND_{2}(L)}$ ist als ${\displaystyle AND_{2}(L)=\{<x,y>\mid x,y\in L\}}$ definiert. Eine Sprache ${\displaystyle L}$ hat die ${\displaystyle AND_{2}}$-Eigenschaft, wenn ${\displaystyle AND_{2}(L)\preceq _{m}^{p}L}$, sich also die AND-Verknupfung der Sprache wieder polynomiell auf die Sprache selbst reduzieren lasst.

Die folgenden Probleme liegen in der Klasse DP oder sind sogar DP-vollstandig. ^[5]

Neben dem SAT-UNSAT-Problem finden sich hier zahlreiche EXACT-Varianten von Optimierungsproblemen, bei denen man fragt, ob die Losung genau eine gegebene Große k hat, wahrend man bei den NP-Varianten typischerweise nur fragt, ob die Losung großer oder kleiner als ein Wert k ist.

• EXACT TSP : Gegeben eine Instanz des Problem des Handlungsreisenden und eine Zahl k. Ist die kurzeste mogliche Reisestrecke genau k?
• EXACT INDEPENDENT SET : Gegeben ein Graph und eine Zahl k. Enthalt die großte stabile Menge genau k Knoten?
• EXACT KNAPSACK : Gegeben eine Instanz des Rucksackproblems und eine Zahl k. Ist der optimale Wert der Zielfunktion genau k?
• EXACT MAX-CUT : Gegeben ein Graph und eine Zahl k. Hat der maximale Schnitt Gewicht k?
• EXACT MAX-SAT : Gegeben eine aussagenlogische Formel in KNF und eine Zahl k. Ist die maximale Anzahl von Klauseln, die gleichzeitig erfullt werden konnen, genau k? (siehe auch Max-3-SAT )
• CRITICAL SAT : Gegeben eine aussagenlogische Formel F in KNF. Ist F unerfullbar, aber das Loschen jeder beliebigen Klausel macht F erfullbar? ^[6]
• CRITICAL HAMILTON PATH : Gegeben ein Graph. Ist es wahr, dass der Graph keinen Hamiltonweg hat, aber das Hinzufugen jeder beliebigen Kante einen Hamiltonweg erzeugt? ^[6]
• CRITICAL 3-COLORABILITY : Gegeben ein Graph. Ist es wahr, dass der Graph nicht 3-knotenfarbbar ist, aber das Loschen jedes beliebigen Knoten den Graph 3-knotenfarbbar macht? ^[7]

• UNIQUE SAT : Gegeben eine aussagenlogische Formel F in KNF. Gibt es genau eine Interpretation, die F erfullt?

• Gerd Wechsung : On the Boolean closure of NP. In: Lothar Budach (Hrsg.): Fundamentals of Computation Theory (=  Lecture Notes in Computer Science ). Band   199 . Springer, Berlin Heidelberg 1985, ISBN 978-3-540-15689-5 , S.   485–493 , doi : 10.1007/BFb0028832 .  
• Richard Chang, Jim Kadin: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection. In: SIAM J. Comput. Band   25 , Nr.   2 , 1996, S.   340?354 , doi : 10.1137/S0097539790178069 .  

• BH . In: Complexity Zoo. (englisch)
• DP . In: Complexity Zoo. (englisch)

1. ↑ ^{a b} Johannes Kobler, Uwe Schoning, Klaus Wagner: The Difference and Truth-Table Hierarchies for NP . In: Theoretical Informatics and Applications . Band   21 , Nr.   4 , 1987, S.   419?43 .  
2. ↑ More Complicated Questions About Maxima and Minima, and Some Closures of NP . In: Theoret. Comput. Sci. Band   51 , 1987, S.   53?80 .  
3. ↑ C. H. Papadimitriou and M. Yannakakis. The complexity of facets (and some facets of complexity). Journal of Computer and System Sciences, 28(2):244?259, 1982.
4. ↑ Richard Chang, Jim Kadin: On Computing Boolean Connectives of Characteristic Functions. Mathematical Systems Theory 28(3): 173?198 (1995) doi:10.1007/BF01303054 .
5. ↑ Christos H. Papadimitriou: Computational complexity. Chapter 17. Academic Internet Publ. 2007, ISBN 978-1-4288-1409-7 , pp. 1?49
6. ↑ ^{a b} Christos H. Papadimitriou , David Wolfe: The complexity of facets resolved . In: Journal of Computer and System Sciences . Band   37 , Nr.   1 , 1988, S.   2?13 , doi : 10.1016/0022-0000(88)90042-6 .  
7. ↑ Jin-yi Cai, Gabriele E. Meyer: Graph minimal uncolorability is DP-complete. In: SIAM Journal on Computing . Band   16 , Nr.   2 , 1987, S.   259 - 277 , doi : 10.1137/0216022 .