The Boolean Hierarchy I: Structural Properties
Authors:
- Jin-Yi CaiJCJin-Yi Cai
- Thomas GundermannTGThomas Gundermann
- Juris HartmanisJHJuris Hartmanis
- Lane A. HemachandraLHLane A. Hemachandra
- Vivian SewelsonVSVivian Sewelson
- Klaus WagnerKWKlaus Wagner
- Gerd WechsungGWGerd Wechsung
- 1 December 1988
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 17 (6) , 1232-1252
Abstract
In this paper, we study the complexity of sets formed by boolean operations (union, intersection, and complement) on NP sets. These are the sets accepted by trees of hardware with NP predicates as leaves, and together these form the boolean hierarchy. We present many results about the structure of the boolean hierarchy: separation and immunity results, natural complete languages, and structural asymmetries between complementary classes. We show that in some relativized worlds the boolean hierarchy is infinite, and that for every k there is a relativized world in which the boolean hierarchy extends exactly k levels. We prove natural languages, variations of VERTEX COVER, complete for the various levels of the boolean hierarchy. We show the following structural asymmetry: though no set in the boolean hierarchy is ${\text{D}}^{\text{P}} $-immune, there is a relativized world in which the boolean hierarchy contains ${\text{coD}}^{\text{P}} $-immune sets. Thus, this paper explores the structural properties of the boolean hierarchy. A companion paper [J. Cai et al., SIAM J. Comput. 18 (1989), to appear] uses the boolean hierarchy to extend known results on small circuits [R. Karp and R. Lipton, Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309], sparse sets in NP-P [J. Hartmanis, N. Immerman, and V. Sewelson, Proc.15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391], and counting classes [A. Blass and Y. Gurevich, Inform. and Control, 55 (1982), pp. 80–88].Keywords
This publication has 21 references indexed in Scilit:
- The Boolean Hierarchy II: ApplicationsSIAM Journal on Computing, 1989
- The Polynomial Time Hierarchy Collapses If the Boolean Hierarchy CollapsesSIAM Journal on Computing, 1988
- Graph Minimal Uncolorability is ${\text{D}}^{\text{p}} $-CompleteSIAM Journal on Computing, 1987
- Complexity classes without machines: On complete languages for UPLecture Notes in Computer Science, 1986
- The boolean hierarchy: Hardware over NP1986
- On sparse oracles separating feasible complexity classes1986
- Relativized polynomial hierarchies extending two levelsTheory of Computing Systems, 1984
- On the unique satisfiability problemInformation and Control, 1982
- On relativization and the existence of complete sets1982
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1SIAM Journal on Computing, 1981