The top part of Figure 1.1 shows some classes from the (truth-table) bounded-query and boolean hierarchies. It is well known that if either of these hierarchies collapses at a given level, then all higher levels of that hierarchy collapse to that same level. This is a standard "upward translation of equality" that has been known for over a decade. The issue of whether these hierarchies can translate equality downwards has proven vastly more challenging. In particular, with regard to Figure 1.1, consider the following claim: \[ \psigkmtt = \psigkmponett \implies \diffmsigk = \codiffmsigk = \bh(\sigmak). (*) \] Until recently, it was not known whether (*) ever held, except for the degenerate cases m = 0 and k = 0. Then Hemaspaandra, Hemaspaandra, and Hempel [SIAM J. Comput., 28 (1999), pp. 383--393] proved that (*) holds for all m, for k > 2. Buhrman and Fortnow [J. Comput. System Sci., 59 (1999), pp. 182--199] then showed that, when k = 2, (*) holds for the case m = 1. In this paper, we prove that for the case k = 2, (*) holds for all values of m. Since there is an oracle relative to which "for k = 1, (*) holds for all m" fails (see Buhrman and Fortnow), our achievement of the k = 2 case cannot be strengthened to k = 1 by any relativizable proof technique. The new downward translation we obtain also tightens the collapse in the polynomial hierarchy implied by a collapse in the bounded-query hierarchy of the second level of the polynomial hierarchy.

The nondeterministic advice complexity of the P-selective sets is known to be exactly linear. Regarding the deterministic advice complexity of the P-selective sets---i.e., the amount of Karp--Lipton advice needed for polynomial-time machines to recognize them in general---the best current upper bound is quadratic [K. Ko, J. Comput. System Sci., 26 (1983), pp. 209--221] and the best current lower bound is linear [L. Hemaspaandra and L. Torenvliet, Theoret. Comput. Sci., 154 (1996), pp. 367--377]. We prove that every associatively P-selective set is commutatively, associatively P-selective. Using this, we establish an algebraic sufficient condition for the P-selective sets to have a linear upper bound (which thus would match the existing lower bound) on their deterministic advice complexity: If all P-selective sets are associatively P-selective, then the deterministic advice complexity of the P-selective sets is linear. The weakest previously known sufficient condition was P = NP. We also establish related results for algebraic properties of, and advice complexity of, the nondeterministically selective sets.

Downward collapse (also known as upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide an unqualified downward collapse result completely within the polynomial hierarchy. In particular, we prove that, for k > 2, if ${\rm P}^{\Sigma^p_k[1]} = {\rm P}^{\Sigma^p_k[2]}$ then $\Sigma^p_k = \Pi^p_k = {\rm PH}$. We extend this to obtain a more general downward collapse result.

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.