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 zwei Komplexitätsklassen, dann
, wobei das Komplement von ist.
Ausgehend von NP können die verschiedenen Ebenen der Booleschen Hierarchie (BH) definiert werden:
Zum Beispiel und .
Die Boolesche Hierarchie (BH) wird dann als die Vereinigung aller ihrer Level definiert, also .
Alternative Charakterisierung Die Boolesche Hierarchie kann für auch wie folgt charakterisiert werden:
Charakterisierung über die symmetrische Differenz Seien zwei Komplexitätsklassen, dann ist , wobei die symmetrische Differenz darstellt.
Dann lässt sich als bzw. 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 von verschiedenen Instanzen des Problems A, sodass wann immer gilt, auch gilt. Zu entscheiden, ob in einer Folge der Länge eine ungerade Anzahl Instanzen in A sind, ist -vollständig. Zu entscheiden, ob in einer Folge der Länge eine gerade Anzahl Instanzen in A sind, ist -vollständig.
Beziehungen zu anderen Komplexitätsklassen Sollte die Boolesche Hierarchie kollabieren, dann kollabiert auch die polynomielle Hierarchie zu .
und
Die Klasse DP Die Klasse DP (Difference Polynomial Time) wurde von Papadimitriou and Yannakakis eingeführtC. 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. und ist wie folgt definiert. Eine Sprache ist in DP genau dann, wenn es Sprachen gibt, so dass .
Damit entspricht DP dem zweiten Level 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 von aussagenlogischen Formeln (wahlweise in 3-KNF). Die Problemstellung ist zu entscheiden, ob erfüllbar (SAT) und unerfüllbar (UNSAT) ist.
Alternative Charakterisierung der DP-Vollständigkeit Die vollständigen Probleme der Klasse DP können auch wie folgt charakterisiert werdenRichard Chang, Jim Kadin: On Computing Boolean Connectives of Characteristic Functions. Mathematical Systems Theory 28(3): 173–198 (1995) doi:10.1007/BF01303054..
Eine Sprache L ist DP-vollständig genau dann, wenn alle der folgenden Bedingungen erfüllt sind:
ist NP-schwer ist coNP-schwer hat die -Eigenschaft: Die Sprache ist als definiert. Eine Sprache hat die -Eigenschaft, wenn , 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.Christos H. Papadimitriou: Computational complexity. Chapter 17. Academic Internet Publ. 2007, ISBN 978-1-4288-1409-7, pp. 1–49 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
Weblinks
Einzelnachweise
Kategorie:Komplexitätstheorie