The Boolean Hierarchy II: Applications

Abstract

The Boolean Hierarchy I: Structural Properties [J. Cai et al., SIAM J. Comput ., 17 (1988), pp. 1232–252] explores the structure of the boolean hierarchy, the closure of NP with respect to boolean operations. This paper uses the boolean hierarchy as a tool with which to extend and explain three important results in structural complexity theory. (1) Hartmanis, Immerman, and Sewelson [ Proc. 15th Annual Symposium on the Theory of Computation, 1983, pp. 382–391] showed that ${\text{E}} = {\text{NE}}$ if and only if ${\text{NP}} - {\text{P}}$ contains no sparse sets. In this paper it is shown that this reflects a behavior of the boolean hierarchy. When ${\text{E}} = {\text{NE}}$, sparse sets fall from alternate levels of the boolean hierarchy (Fig. 2(a)). Furthermore, it is shown that capturable sets (i.e., subsets of sparse NP sets) are banished from the boolean hierarchy when ${\text{E}} = {\text{NE}}:{\text{E}} = {\text{NE}}$ implies that ${\text{BH}} - {\text{P}}$ has no capturable sets. (2) Counting classes are natural candidates as complete languages for the levels of the boolean hierarchy. The authors show that in relativized worlds counting classes are not complete for the levels of the boolean hierarchy. Relatedly, the work of Blass and Gurevich [Inform, and Control, 55 (1982), pp. 80–88] is extended and it is concluded that counting classes are weak in some relativized worlds. (3) Karp and Lipton [Proc. 12th Annual Symposium on the Theory of Computation, 1980, pp. 302–309] showed that if NP has a sparse oracle (i.e., if there is a sparse set S so ${\text{NP}} \subseteq {\text{P}}^S $; equivalently, if NP has small circuits), then the polynomial hierarchy collapses to ${\text{NP}}^{{\text{NP}}} $. The authors demonstrate that this cannot be much improved. There is a relativized world in which NP has a sparse oracle, yet the boolean hierarchy is infinite. Thus no proof that relativizes can show: NP has .a sparse oracle implies that the polynomial hierarchy equals the boolean hierarchy. The results of this paper present new ideas and techniques, and put previous results about NP and ${\text{D}}^{\text{P}} $ in a richer perspective. Throughout, the emphasis is on the structure of the boolean hierarchy and its relations with more common classes.