Boolesche Hierarchie

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

Definition

Zunächst definieren wir boolesche Konnektive für Komplexitätsklassen. Seien ${\mathcal {C}},{\mathcal {C'}}$ zwei Komplexitätsklassen, dann

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

Ausgehend von NP können die verschiedenen Ebenen der Booleschen Hierarchie (BH) definiert werden:

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

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

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

Alternative Charakterisierung

Die Boolesche Hierarchie kann für $k\geq 1$ auch wie folgt charakterisiert werden^[1]:

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

Charakterisierung über die Symmetrische Differenz

Seien ${\mathcal {C}},{\mathcal {C'}}$ zwei Komplexitätsklassen, dann ist

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

Dann lässt sich $BH_{k}$ als $BH_{k}=BH_{k-1}\oplus NP$ bzw. $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 $x_{1},\dots x_{m}$ von verschiedenen Instanzen des Problems A, sodass wann immer $x_{i}\in A$ gilt, auch $x_{i-1}\in A$ gilt.

Zu entscheiden, ob in einer Folge der Länge $2k$ eine ungerade Anzahl an Instanzen in A sind, ist $BH_{2k}$ -vollständig.
Zu entscheiden, ob in einer Folge der Länge $2k+1$ eine gerade Anzahl an Instanzen in A sind, ist $BH_{2k+1}$ -vollständig.

Beziehungen zu anderen Komplexitätsklassen

Sollte die Boolesche Hierarchie kollabieren, dann kollabiert auch die polynomielle Hierarchie zu $\Sigma _{3}^{\rm {P}}$ .
$BH\subseteq \Delta _{2}^{\rm {P}}$
$NP\subseteq BH$ und $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 $L$ ist in DP genau dann, wenn es Sprachen $\textstyle L_{1}\in NP,L_{2}\in coNP$ gibt, so dass $L=L_{1}\cap L_{2}$ .

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

SAT-UNSAT-Problem

Das SAT-UNSAT-Problem ist das kanonische vollständige Problem für die Klasse DP.

Eine SAT-UNSAT-Instanz besteht aus einem Paar $(\phi ,\psi )$ von aussagenlogischen Formeln (wahlweise in 3-KNF). Die Problemstellung ist zu entscheiden, ob $\phi$ erfüllbar (SAT) und $\psi$ unerfüllbar (UNSAT) ist.

Alternative Charakterisierung der DP-Vollständigkeit

Die vollständigen Probleme der Klasse DP können auch wie folgt charakterisiert werden^[4].

Eine Sprache L ist DP-vollständig genau dann, wenn alle der folgenden Bedingungen erfüllt sind:

$L\in DP$
$L$ ist NP-schwer
$L$ ist coNP-schwer
$L$ hat die $AND_{2}$ -Eigenschaft: Die Sprache $AND_{2}(L)$ ist als $AND_{2}(L)=\{<x,y>\mid x,y\in L\}$ definiert. Eine Sprache $L$ hat die $AND_{2}$ -Eigenschaft, wenn $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 in der Klasse DP oder sind sogar DP-vollständig.^[5]

Vollständige Probleme

Neben dem SAT-UNSAT-Problem finden sich hier zahlreiche EXACT-Varianten von Optimierungsproblemen, bei denen man fragt, ob die Lösung genau eine gegebene Größe k hat, während man bei den NP-Varianten typischerweise nur fragt, ob die Lösung größer oder kleiner als 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, dass 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, dass 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

↑ ^a ^b 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.
↑ More Complicated Questions About Maxima and Minima, and Some Closures of NP. In: Theoret. Comput. Sci. Band 51, 1987, S. 53–80.
↑ 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.
↑ Richard Chang, Jim Kadin: On Computing Boolean Connectives of Characteristic Functions. Mathematical Systems Theory 28(3): 173–198 (1995) doi:10.1007/BF01303054.
↑ Christos H. Papadimitriou: Computational complexity. Chapter 17. Academic Internet Publ. 2007, ISBN 978-1-4288-1409-7, pp. 1–49
↑ ^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.
↑ 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.

[Köbler87-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.

[Wagner87-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

[PapadimitriouW88-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.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Algorithmus

Boolesche Hierarchie

Inhaltsverzeichnis

Definition

Alternative Charakterisierung

Charakterisierung über die Symmetrische Differenz

Vollständige Probleme

Beziehungen zu anderen Komplexitätsklassen