View source for Boolean hierarchy

{{Short description|Difficulty measures for computer science problems}}
The '''boolean hierarchy''' is the [[Hierarchy (mathematics)|hierarchy]] of [[Algebra of sets|boolean combinations]] ([[Intersection (set theory)|intersection]], union and [[Complement (complexity)|complement]]ation) of NP sets. Equivalently, the boolean hierarchy can be described as the class of [[Boolean circuit|boolean circuit]]s over [[NP (complexity)|NP]] predicates. A collapse of the boolean hierarchy would imply a collapse of the [[Polynomial hierarchy|polynomial hierarchy]].<ref name=ChangK96>{{cite journal
| title = The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection
| author = Chang, R.
| author2 = Kadin, J.
| doi = 10.1137/S0097539790178069
| journal = SIAM J. Comput.
| year = 1996
| volume = 25
| pages = 340–354
| issue = 2
| citeseerx = 10.1.1.77.4186
}}</ref>

== Formal definition ==

BH is defined as follows:<ref>{{ComplexityZoo|Class BH|B#bh}}</ref>
* BH<sub>1</sub> is NP.
* BH<sub>2''k''</sub> is the class of languages which are the [[Intersection (set theory)|intersection]] of a language in BH<sub>2''k''-1</sub> and a language in coNP.
* BH<sub>2''k''+1</sub> is the class of languages which are the union of a language in BH<sub>2''k''</sub> and a language in NP.
* BH is the union of all the BH<sub>i</sub> classes.

== Derived classes ==

* DP (Difference Polynomial Time) is BH<sub>2</sub>.<ref>{{ComplexityZoo|Class DP|D#dp}}</ref>

== Equivalent definitions ==

Defining the conjunction and the disjunction of classes as follows allows for
more compact definitions. The conjunction of two classes contains the languages that are the intersection of a language of the first class and a language of the second class. Disjunction is defined in a similar way with the union in place of the intersection.
* C &and; D = { A &cap; B | A &isin; C &nbsp; B &isin; D }
* C &or;  D = { A &cup; B | A &isin; C &nbsp; B &isin; D }

According to this definition, DP = NP &and; coNP. The other classes of the Boolean hierarchy can be defined as follows.

:<math>\mathsf{BH}_{2k} = \mathsf{coNP} \wedge \mathsf{BH}_{2k-1}</math>

:<math>\mathsf{BH}_{2k+1} = \mathsf{NP} \vee \mathsf{BH}_{2k}</math>

The following equalities can be used as alternative definitions of the classes of the Boolean hierarchy:<ref name=Wagner87>{{cite journal
| title = More Complicated Questions About Maxima and Minima, and Some Closures of NP
| author = Wagner, K.
| doi = 10.1016/0304-3975(87)90049-1
| journal = Theoret. Comput. Sci.
| year = 1987
| volume = 51
| issue = 1–2
| pages = 53–80
| doi-access = free
}}</ref>

:<math>\mathsf{BH}_{2k} = \bigvee_{i=1}^k \mathsf{DP}</math>

:<math>\mathsf{BH}_{2k+1} = \mathsf{NP} \vee \bigvee_{i=1}^k \mathsf{DP}</math>

Alternatively,<ref name=RiegeRothe06>{{cite journal
| title = Completeness in the Boolean Hierarchy: Exact-Four-Colorability, Minimal Graph Uncolorability, and Exact Domatic Number Problems - a Survey
| author = Riege, T.
| author2 = Rothe, J.
| journal = J. Univers. Comput. Sci.
| year = 2006
| volume = 12
| pages = 551–578
| issue = 5
}}</ref> for every ''k'' &ge; 3:

:<math>\mathsf{BH}_k = \mathsf{DP} \vee \mathsf{BH}_{k-2}</math>

== Hardness ==

Hardness for classes of the Boolean hierarchy can be proved by showing a reduction from a number of instances of an arbitrary NP-complete problem A. In particular, given a sequence {''x''<sub>1</sub>, ...  ''x<sub>m</sub>''} of instances of A such that ''x<sub>i</sub>'' &isin; A implies ''x''<sub>''i''-1</sub> &isin; A, a reduction is required that produces an instance ''y'' such that ''y'' &isin; B if and only if the number of ''x<sub>i</sub>'' &isin; A is odd or even:<ref name=Wagner87 />

* BH<sub>2''k''</sub>-hardness is proved if {{tmath|1=m=2k}} and the number of ''x<sub>i</sub>'' &isin; A is odd
* BH<sub>2''k''+1</sub>-hardness is proved if {{tmath|1=m=2k+1}} and the number of ''x<sub>i</sub>'' &isin; A is even

Such reductions work for every fixed {{mvar|k}}. If such reductions exist for arbitrary {{mvar|k}}, the problem is hard for P<sup>NP[''O''(log ''n'')]</sup>.

== References ==
<references />

{{ComplexityClasses}}

[[Category:Hierarchy]]


{{computer science stub}}

{{Sourceattribution|Boolean hierarchy}}