Extending Downward Collapse from 1-versus-2 Queries to m -versus- m + 1 Queries
Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel⋆ · SIAM Journal on Computing · 2005
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.