Boolean hierarchy

The Boolean hierarchy is a hierarchy of complexity classes that are formed as Boolean combinations of NP problems.

definition

First we define Boolean connections for complexity classes. Be two complexity classes, then ${\displaystyle {\mathcal {C}},{\mathcal {C'}}}$

• ${\displaystyle {\mathcal {C}}\wedge {\mathcal {C'}}=\{L_{1}\cap L_{2}\mid L_{1}\in {\mathcal {C}},L_{2}\in {\mathcal {C'}}\}}$
• ${\displaystyle {\mathcal {C}}\vee {\mathcal {C'}}=\{L_{1}\cup L_{2}\mid L_{1}\in {\mathcal {C}},L_{2}\in {\mathcal {C'}}\}}$
• ${\displaystyle co{\mathcal {C}}=\{L\mid {\bar {L}}\in {\mathcal {C}}\}}$where is the complement of . ${\displaystyle {\bar {L}}}$ ${\displaystyle {L}}$

Based on NP, the different levels of the Boolean hierarchy (BH) can be defined:

• ${\displaystyle BH_{1}=NP}$
• ${\displaystyle BH_{2k}=coNP\wedge BH_{2k-1}}$
• ${\displaystyle BH_{2k+1}=NP\vee BH_{2k}}$

For example and . ${\displaystyle BH_{2}=coNP\wedge NP}$ ${\displaystyle BH_{3}=NP\vee (coNP\wedge NP)}$

The Boolean hierarchy (BH) is then defined as the union of all its levels, ie . ${\displaystyle BH=\bigcup _{i\geq 1}BH_{i}}$

Alternative characterization

The Boolean hierarchy can also be characterized as follows: ${\displaystyle k\geq 1}$

• ${\displaystyle BH_{2k}=\bigvee _{i=1}^{k}(NP\land coNP)}$
• ${\displaystyle BH_{2k+1}=NP\vee \bigvee _{i=1}^{k}(NP\land coNP)}$

Characterization via the symmetrical difference

If there are two complexity classes, then is ${\displaystyle {\mathcal {C}},{\mathcal {C'}}}$

• ${\displaystyle {\mathcal {C}}\oplus {\mathcal {C'}}=\{L_{1}\bigtriangleup L_{2}\mid L_{1}\in {\mathcal {C}},L_{2}\in {\mathcal {C'}}\}}$where represents the symmetrical difference . ${\displaystyle \bigtriangleup }$

Then can be characterized as or . ${\displaystyle BH_{k}}$ ${\displaystyle BH_{k}=BH_{k-1}\oplus NP}$ ${\displaystyle BH_{k}=\bigoplus _{i=1}^{k}NP}$

Complete problems

Starting from any NP-complete problem A (e.g. SAT ), one can define a family of complete problems for different levels of the Boolean hierarchy as follows.

Given a consequences of different instances of the problem so that whenever A is also true. ${\displaystyle x_{1},\dots x_{m}}$ ${\displaystyle x_{i}\in A}$ ${\displaystyle x_{i-1}\in A}$

• It is complete to decide whether there are an odd number of instances in A in a sequence of length . ${\displaystyle 2k}$ ${\displaystyle BH_{2k}}$
• To decide whether there are an even number of instances in A in a sequence of length is complete. ${\displaystyle 2k+1}$ ${\displaystyle BH_{2k+1}}$

Relationships to other complexity classes

• If the boolean hierarchy collapses, then collapse the polynomial hierarchy to . ${\displaystyle \Sigma _{3}^{\rm {P}}}$
• ${\displaystyle BH\subseteq \Delta _{2}^{\rm {P}}}$
• ${\displaystyle NP\subseteq BH}$ and ${\displaystyle coNP\subseteq BH}$

The class DP

The class DP (Difference Polynomial Time) was introduced by Papadimitriou and Yannakakis and is defined as follows. A language is in DP if and only if there are languages such that . ${\displaystyle L}$ ${\displaystyle \textstyle L_{1}\in NP,L_{2}\in coNP}$ ${\displaystyle L=L_{1}\cap L_{2}}$

DP thus corresponds to the second level of the Boolean hierarchy. ${\displaystyle BH_{2}}$

SAT-UNSAT problem

The SAT-UNSAT problem is the canonical complete problem for the class DP.

A SAT-UNSAT instance consists of a pair of propositional formulas (optionally in 3- CNF ). The problem has to be decided whether it is feasible (SAT) and unsatisfiable (UNSAT). ${\displaystyle (\phi ,\psi )}$ ${\displaystyle \phi }$ ${\displaystyle \psi }$

Alternative characterization of DP completeness

The complete problems of class DP can also be characterized as follows.

A language L is DP complete if and only if all of the following conditions are met:

1. ${\displaystyle L\in DP}$
2. ${\displaystyle L}$ NP is difficult
3. ${\displaystyle L}$ coNP is difficult
4. ${\displaystyle L}$has the property: The language is defined as. A language has the property, if , that is, the AND operation of the language can be reduced polynomially to the language itself . ${\displaystyle AND_{2}}$ ${\displaystyle AND_{2}(L)}$ ${\displaystyle AND_{2}(L)=\{<x,y>\mid x,y\in L\}}$ ${\displaystyle L}$ ${\displaystyle AND_{2}}$ ${\displaystyle AND_{2}(L)\preceq _{m}^{p}L}$

Problems in class DP

The following problems are in class DP or even DP complete.

Complete problems

In addition to the SAT-UNSAT problem, there are numerous EXACT variants of optimization problems in which one asks whether the solution has exactly a given quantity k, while with the NP variants one typically only asks whether the solution is greater or less than a Value k is.

• EXACT TSP : Given an instance of the traveling salesman's problem and a number k. Is the shortest possible travel distance exactly k?
• EXACT INDEPENDENT SET : Given a graph and a number k. Does the largest stable set contain exactly k nodes?
• EXACT KNAPSACK : Given an instance of the backpack problem and a number k. Is the optimal value of the objective function exactly k?
• EXACT MAX-CUT : Given a graph and a number k. Does the maximum cut weight k?
• EXACT MAX-SAT : Given a propositional formula in CNF and a number k. Is the maximum number of clauses that can be satisfied simultaneously exactly k? (see also Max-3-SAT )
• CRITICAL SAT : Given a propositional formula F in CNF. Is F unsatisfiable, but deleting any clause makes F satisfiable?
• CRITICAL HAMILTON PATH : Given a graph. Is it true that the graph does not have a Hamilton path, but adding any edge creates a Hamilton path?
• CRITICAL 3-COLORABILITY : Given a graph. Is it true that the graph is not 3-vertex colorable , but deleting any node makes the graph 3-vertex colorable?

Problems in DP

• UNIQUE SAT : Given a propositional formula F in CNF. Is there exactly one interpretation that satisfies F?

literature

• Gerd Wechsung : On the Boolean closure of NP. In: Lothar Budach (Ed.): Fundamentals of Computation Theory (=  Lecture Notes in Computer Science ). tape 199 . Springer, Berlin Heidelberg 1985, ISBN 978-3-540-15689-5 , pp. 485-493 , doi : 10.1007 / BFb0028832 .
• Richard Chang, Jim Kadin: The Boolean Hierarchy and the Polynomial Hierarchy: A Closer Connection. In: SIAM J. Comput. tape 25 , no. 2 , 1996, p. 340-354 , doi : 10.1137 / S0097539790178069 .

Web links

• Bra . In: Complexity Zoo. (English)
• DP . In: Complexity Zoo. (English)

Individual evidence

1. ↑ ^{a b} Johannes Köbler, Uwe Schöning, Klaus Wagner: The Difference and Truth-Table Hierarchies for NP . In: Theoretical Informatics and Applications . tape 21 , no. 4 , 1987, pp. 419-43 .
2. ↑ More Complicated Questions About Maxima and Minima, and Some Closures of NP . In: Theoret. Comput. Sci. tape 51 , 1987, pp. 53-80 .
3. ^ CH 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 . tape 37 , no. 1 , 1988, p. 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 . tape 16 , no. 2 , 1987, pp. 259 - 277 , doi : 10.1137 / 0216022 .