More than a quarter of a century ago, the question of the complexity of determining whether a given Boolean formula is minimal motivated Meyer and Stockmeyer to define the polynomial hierarchy. This problem (in the standard formalized version---that of Garey and Johnson) has been known for decades to be coNP-hard and in NP NP , and yet no one had even been able to establish (many-one) NP-hardness. In this paper, we show that and more: The problem in fact is (many-one) hard for parallel access to NP.

We study the effect of queryorder on computational power and show that ${\rm P}^{{\rm BH}_j[1]:{\rm BH}_k[1]}$\allowbreak---the languages computable via a polynomial-time machine given one query to the jth level of the boolean hierarchy followed by one query to the kth level of the boolean hierarchy---equals ${\rm R}_{{j+2k-1}{\scriptsize\mbox{-tt}}}^{p}({\rm NP})$ if j is even and k is odd and equals ${\rm R}_{{j+2k}{\scriptsize\mbox{-tt}}}^{p}({\rm NP})$ otherwise. Thus unless the polynomial hierarchy collapses it holds that, for each $1\leq j \leq k$, ${\rm P}^{{\rm BH}_j[1]:{\rm BH}_k[1]} = {\rm P}^{{\rm BH}_k[1]:{\rm BH}_j [1]} \iff (j=k) \lor (j\mbox{ is even}\, \land k=j+1)$. We extend our analysis to apply to more general query classes.

First we obtain two new results considering the inclusion problem of polynomial time frequency classes with equal numbers of errors: 1) (m, m+d) P/spl supe/(m+1, m+d+1) P for m<2/sup d/; and 2) (m, m+d) P=(m+1, m+d+1) P for m/spl ges/c(d) where c(d) is large enough. This disproves a conjecture of Kinber (1975). Next we give a transparent proof of a generalization of Kinber's result that there exist arbitrarily complex problems admitting a polynomial time frequency computation. Several corollaries provide more insight in the structure of the hierarchy of polynomial time frequency classes.

We investigate the computational complexity of the minimization problem for Boolean formulas. Depending on the definition, these problems are trivially in /spl Sigma//sub 2//sup P/ or II/sub 2//sup P/, and these are the best upper bounds known. The only previously known lower bounds are also trivial, and are coNP lower bounds at best, thus leaving quite a large gap between the upper and lower bounds. In this paper, we prove much better lower bounds: hardness for parallel access to NP for those cases in which coNP was the best previously known lower bound, and coNP-hardness for the case in which no lower bound was previously known.

We show that probabilistic polynomial time (PP) is closed under polynomial-time parity reductions. As corollaries, we show that several complexity classes are contained in PP.

This paper completely characterizes the Θkp levels of the polynomial hierarchy in terms of Kolmogorov complexity. From the characterization, it follows that the Θkp and Δkp levels of the polynomial hierarchy are equal if and only if every Δkp language is accepted by some Δkp machine whose pronouncements (query answers) are Kolmogorov simple. Analogous results are obtained for the exponential hierarchy.

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.

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].