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 $𝒞,{𝒞}^{\prime }$ zwei Komplexitätsklassen, dann

• $𝒞\wedge {𝒞}^{\prime }=\{L_1\cap L_2\mid L_1\in 𝒞,L_2\in {𝒞}^{\prime }\}$
• $𝒞\vee {𝒞}^{\prime }=\{L_1\cup L_2\mid L_1\in 𝒞,L_2\in {𝒞}^{\prime }\}$
• $co𝒞=\{L\mid \overline{L}\in 𝒞\}$, wobei $\overline{L}$ das Komplement von $L$ ist.

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

• $B{H}_1=NP$
• $B{H}_{2k}=coNP\wedge B{H}_{2k-1}$
• $B{H}_{2k+1}=NP\vee B{H}_{2k}$

Zum Beispiel $B{H}_2=coNP\wedge NP$ und $B{H}_3=NP\vee (coNP\wedge NP)$.

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

Alternative Charakterisierung

Die Boolesche Hierarchie kann für $k\ge 1$ auch wie folgt charakterisiert werden:

• $B{H}_{2k}=\underset{i=1}{\overset{k}{\bigvee }}(NP\wedge coNP)$
• $B{H}_{2k+1}=NP\vee \underset{i=1}{\overset{k}{\bigvee }}(NP\wedge coNP)$

Charakterisierung über die symmetrische Differenz

Seien $𝒞,{𝒞}^{\prime }$ zwei Komplexitätsklassen, dann ist

• $𝒞\oplus {𝒞}^{\prime }=\{L_1△L_2\mid L_1\in 𝒞,L_2\in {𝒞}^{\prime }\}$, wobei $△$ die symmetrische Differenz darstellt.

Dann lässt sich $B{H}_k$ als $B{H}_k=B{H}_{k-1}\oplus NP$ bzw. $B{H}_k=\underset{i=1}{\overset{k}{⨁}}NP$ charakterisieren.

Vollständige Probleme

Ausgehend von einem beliebigen 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.

Gegeben sei eine Folge $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 Instanzen in A sind, ist $B{H}_{2k}$-vollständig.
• Zu entscheiden, ob in einer Folge der Länge $2k+1$ eine gerade Anzahl Instanzen in A sind, ist $B{H}_{2k+1}$-vollständig.

Beziehungen zu anderen Komplexitätsklassen

• Sollte die Boolesche Hierarchie kollabieren, dann kollabiert auch die polynomielle Hierarchie zu ${\mathrm{\Sigma }}_3^{\mathrm{P}}$.
• $BH\subseteq {\mathrm{\Delta }}_2^{\mathrm{P}}$
• $NP\subseteq BH$ und $coNP\subseteq BH$

Die Klasse DP

Die Klasse DP (Difference Polynomial Time) wurde von Papadimitriou and Yannakakis eingeführt und ist wie folgt definiert. Eine Sprache $L$ ist in DP genau dann, wenn es Sprachen $L_1\in NP,L_2\in coNP$ gibt, so dass $L=L_1\cap L_2$.

Damit entspricht DP dem zweiten Level $B{H}_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 $(\varphi ,\psi )$ von aussagenlogischen Formeln (wahlweise in 3-KNF). Die Problemstellung ist zu entscheiden, ob $\varphi$ 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.

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

1. $L\in DP$
2. $L$ ist NP-schwer
3. $L$ ist coNP-schwer
4. $L$ hat die $AN{D}_2$-Eigenschaft: Die Sprache $AN{D}_2(L)$ ist als $AN{D}_2(L)=\{<x,y>\mid x,y\in L\}$ definiert. Eine Sprache $L$ hat die $AN{D}_2$-Eigenschaft, wenn $AN{D}_2(L)\underset{m}{\overset{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.

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

Probleme in DP

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

Literatur

• Vorlage:Literatur
• Vorlage:Literatur

Weblinks

• Vorlage:Complexity Zoo
• Vorlage:Complexity Zoo