Boolesche Hierarchie

Das Boolesche Hierarchie ist der Hierarchie von Boolesche Kombinationen (Überschneidung, Union und Ergänzung) von Np Sets. Äquivalent kann die boolesche Hierarchie als Klasse von beschrieben werden Boolesche Schaltungen Über Np Prädikate. Ein Zusammenbruch der booleschen Hierarchie würde einen Zusammenbruch der Polynomhierarchie.[1]

Formale Definition

BH ist wie folgt definiert:[2]

  • BH1 ist Np.
  • BH2k ist die Klasse von Sprachen, die die sind Überschneidung einer Sprache in BH2k-1 und eine Sprache in Conp.
  • BH2k+1 ist die Klasse von Sprachen, die die sind Union einer Sprache in BH2k und eine Sprache in Np.
  • BH ist die Vereinigung des BHi

Abgeleitete Klassen

  • DP (Differenzpolynomzeit) ist BH2.[3]

Äquivalente Definitionen

Das Definieren der Konjunktion und die Disjunktion von Klassen wie folgt ermöglicht kompaktere Definitionen. Die Konjunktion von zwei Klassen enthält die Sprachen, die den Schnittpunkt einer Sprache der ersten Klasse und eine Sprache der zweiten Klasse sind. Die Disjunktion wird auf ähnliche Weise mit der Vereinigung anstelle der Kreuzung definiert.

  • C ∧ d = {a ∩ b | A ∈ C b ∈ D}
  • C ∨ d = {a ∪ b | A ∈ C b ∈ D}

Nach dieser Definition ist dp = np ∧ conp. Die anderen Klassen der Booleschen Hierarchie können wie folgt definiert werden.

Die folgenden Gleichungen können als alternative Definitionen der Klassen der Booleschen Hierarchie verwendet werden:[4]

Alternative,[5] für jeden k ≥ 3:

Härte

Die Härte für Klassen der booleschen Hierarchie kann durch eine Reduzierung einer Reihe von Fällen eines willkürlichen Bestandteils nachgewiesen werden NP-Complete Problem A. insbesondere bei einer Sequenz {x1, ... xm} von Instanzen von einem so, dass xi ∈ A impliziert xi-1 ∈ A, eine Reduktion ist erforderlich, die eine Instanz erzeugt y so dass y ∈ B, wenn und nur wenn die Anzahl von xi ∈ A ist seltsam oder sogar:[4]

  • BH2k-Härtigkeit wird bewiesen, wenn und die Anzahl der Anzahl von xi ∈ A ist seltsam
  • BH2k+1-Härtigkeit wird bewiesen, wenn und die Anzahl der Anzahl von xi ∈ A ist gerade

Solche Reduzierungen funktionieren für jeden festgelegten k. Wenn solche Reduzierungen für willkürliche bestehen kDas Problem ist für p schwerNp [O(Protokoll n)].

Verweise

  1. ^ Chang, R.; Kadin, J. (1996). "Die Boolesche Hierarchie und die Polynomhierarchie: eine engere Verbindung". Siam J. Comput. 25 (25): 340–354. Citeseerx 10.1.1.77.4186. doi:10.1137/s0097539790178069.
  2. ^ Komplexitätszoo: Klasse BH
  3. ^ Komplexitätszoo: Klasse DP
  4. ^ a b Wagner, K. (1987). "Kompliziertere Fragen zu Maxima und Minima und einigen Schließungen von NP". Theoret. Computer. Sci. 51: 53–80. doi:10.1016/0304-3975 (87) 90049-1.
  5. ^ Riege, T.; Rothe, J. (2006). "Vollständigkeit in der Booleschen Hierarchie: Genau-Farbheit, minimale Grafik-Unfeinbarkeit und exakte Domatic-Zahlenprobleme-eine Umfrage". J. Univers. Computer. Sci. 12 (5): 551–578.