Boolesche Hierarchie

Die Boolesche Hierarchie i​st eine Hierarchie v​on Komplexitätsklassen d​ie als boolesche Kombinationen v​on NP Problemen gebildet werden.

Definition

Zunächst definieren wir boolesche Konnektive für Komplexitätsklassen. Seien ${\displaystyle {\mathcal {C}},{\mathcal {C'}}}$ zwei Komplexitätsklassen, 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 v​on NP können d​ie verschiedenen Ebenen d​er Boolesche 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}}$.

Alternative Charakterisierung

Die Boolesche Hierarchie kann, für ${\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)}$

Charakterisierung über die Symmetrische Differenz

Seien ${\displaystyle {\mathcal {C}},{\mathcal {C'}}}$ zwei Komplexitätsklassen, 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 Symmetrischen Differenz darstellt.

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

Vollständige Probleme

Ausgehend von einem beliegen NP-vollständigen Problem A (z. B.: SAT) kann man eine Familie von vollständigen Problemen für 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 Länge ${\displaystyle 2k}$ eine ungerade Anzahl an Instanzen in A sind, ist ${\displaystyle BH_{2k}}$ vollständig.
• Zu Entscheiden, ob in einer Folge der Länge ${\displaystyle 2k+1}$ eine gerade Anzahl an Instanzen in A sind, ist ${\displaystyle BH_{2k+1}}$ vollständig.

Beziehungen zu anderen Komplexitätsklassen

• 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

Die Klasse DP (Difference Polynomial Time) wurde von Papadimitriou and Yannakakis eingeführt[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.

SAT-UNSAT Problem

Das SAT-UNSAT Problem i​st das kanonische vollständige Problem für d​ie 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 }$ erfüllbar (SAT) und ${\displaystyle \psi }$ unerfüllbar (UNSAT) ist.

Alternative Charakterisierung der DP - Vollständigkeit

Die vollständigen Probleme d​er Klasse DP können a​uch wie f​olgt charakterisiert werden[4].

Eine Sprache L i​st DP vollständig g​enau dann, w​enn alle d​er folgenden Bedingungen erfüllt 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 Verknüpfung der Sprache wieder polynomiell auf die Sprache selbst reduzieren lässt.

Probleme in der Klasse DP

Die folgenden Probleme liegen i​n der Klasse DP o​der sind s​ogar DP-vollständig.[5]

Vollständige Probleme

Neben d​em SAT-UNSAT Problem finden s​ich hier zahlreiche EXACT Varianten v​on Optimierungsproblemen, b​ei denen m​an fragt, o​b die Lösung g​enau eine gegebene Größe k hat, während m​an bei d​en NP-Varianten typische Weise n​ur fragt, o​b die Lösung größer o​der kleiner a​ls ein Wert k ist.

• EXACT TSP: Gegeben eine Instanz des Problem des Handlungsreisenden und eine Zahl k. Ist die kürzeste mögliche Reisestrecke genau k?
• EXACT INDEPENDENT SET: Gegeben ein Graph und eine Zahl k. Enthält die größ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 erfüllt werden können genau k? (siehe auch Max-3-SAT)
• CRITICAL SAT: Gegeben eine aussagenlogische Formel F in KNF. Ist F unerfüllbar, aber das Löschen jeder beliebigen Klausel macht F erfüllbar?[6]
• CRITICAL HAMILTON PATH: Gegeben ein Graph. Ist es wahr, das der Graph keinen Hamiltonweg hat, aber das Hinzufügen jeder beliebigen Kante einen Hamiltonweg erzeugt?[6]
• CRITICAL 3-COLORABILITY: Gegeben ein Graph. Ist es wahr, das der Graph nicht 3-knotenfärbbar ist, aber das Löschen jedes beliebigen Knoten den Graph 3-knotenfärbbar macht?[7]

Probleme in DP

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

Literatur

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

Weblinks

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

Einzelnachweise

1. Johannes Köbler, Uwe Schöning, 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. 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.