Given a p‐order A over a universe of strings (i.e., a transitive, reflexive, antisymmetric relation such that if $(x, y) \in A$, then $|x|$ is polynomially bounded by $|y|$), an interval size function of A returns, for each string x in the universe, the number of strings in the interval between strings $b(x)$ and $t(x)$ (with respect to A), where $b(x)$ and $t(x)$ are functions that are polynomial‐time computable in the length of x. By choosing sets of interval size functions based on feasibility requirements for their underlying p‐orders, we obtain new characterizations of complexity classes. We prove that the set of all interval size functions whose underlying p‐orders are polynomial‐time decidable is exactly #P. We show that the interval size functions for orders with polynomial‐time adjacency checks are closely related to the class FPSPACE(poly). Indeed, FPSPACE(poly) is exactly the class of all nonnegative functions that are an interval size function minus a polynomial‐time computable function. We study two important functions in relation to interval size functions. The function #DIV maps each natural number n to the number of nontrivial divisors of n. We show that #DIV is an interval size function of a polynomial‐time decidable partial p‐order with polynomial‐time adjacency checks. The function #MONSAT maps each monotone boolean formula F to the number of satisfying assignments of F. We show that #MONSAT is an interval size function of a polynomial‐time decidable total p‐order with polynomial‐time adjacency checks. Finally, we explore the related notion of cluster computation.

This paper addresses the problems of counting proof-trees (as introduced by Venkateswaran and Tompa) and counting proof-circuits, a related but seemingly more natural question. These problems lead to a common generalization of straight-line programs which we call polynomial replacement systems {PRSs}. We contribute a classification of these systems and we investigate their complexity. Diverse problems falling within the scope of this study include, for example, counting proof-circuits and evaluating $\{\cup,+\}$-circuits over the natural numbers. A number of complexity results are obtained, including a proof that counting proof-circuits is $\numP$-complete.

We discuss the use of operators of higher types in complexity theory. These are operators ranging over sets of words, i.e. over oracles. Depending on different oracle access mechanisms we consider two types of operators. In particular we examine existential, universal, and bounded-error probabilistic operators. We identify some of the emerging classes and we interpret recent results about interactive protocols in terms of these operators.

Polynomial time machines having restricted access to an NP oracle are investigated. Restricted access means that the number of queries to the oracle is restricted or the way in which the queries are made is restricted (e.g., queries made during truth-table reductions). Very different kinds of such restrictions result in the same or comparable complexity classes. In particular, the class $P^{\text{NP}}[O(\log n)]$ can be characterized in very different ways. Furthermore, the Boolean hierarchy is generalized in such a way that it is possible to characterize $P^{\text{NP}}$ and $P^{\text{NP}}[O(\log n)]$ in terms of the generalization.

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