Boolesche Hierarchie

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

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

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

[Bearbeiten | Quelltext bearbeiten]

Die Boolesche Hierarchie kann für auch wie folgt charakterisiert werden[1]:

Charakterisierung über die Symmetrische Differenz

[Bearbeiten | Quelltext bearbeiten]

Seien zwei Komplexitätsklassen, dann ist

  • , wobei die symmetrische Differenz darstellt.

Dann lässt sich als bzw. charakterisieren.[1]

Vollständige Probleme

[Bearbeiten | Quelltext bearbeiten]

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 von verschiedenen Instanzen des Problems A, sodass wann immer gilt, auch gilt.

  • Zu entscheiden, ob in einer Folge der Länge eine ungerade Anzahl an Instanzen in A sind, ist -vollständig.
  • Zu entscheiden, ob in einer Folge der Länge eine gerade Anzahl an Instanzen in A sind, ist -vollständig.

Beziehungen zu anderen Komplexitätsklassen

[Bearbeiten | Quelltext bearbeiten]
  • Sollte die Boolesche Hierarchie kollabieren, dann kollabiert auch die polynomielle Hierarchie zu .
  • und

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

[Bearbeiten | Quelltext bearbeiten]

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

[Bearbeiten | Quelltext bearbeiten]

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:

  1. ist NP-schwer
  2. ist coNP-schwer
  3. 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

[Bearbeiten | Quelltext bearbeiten]

Die folgenden Probleme liegen in der Klasse DP oder sind sogar DP-vollständig.[5]

Vollständige Probleme

[Bearbeiten | Quelltext bearbeiten]

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]
  • UNIQUE SAT: Gegeben eine aussagenlogische Formel F in KNF. Gibt es genau eine Interpretation, die F erfüllt?
  • 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)

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. 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.
  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.