2001/06/15 by Edith Hemaspaandra, Hemaspaandra, Edith, Lane A. Hemaspaandra +3
Computer Science · #Computational Complexity (cs.CC) #F.1.2 #F.1.3 #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0106037
22 pages. Also appears as URCS technical report
arxiv created 2001/06/15 · arxiv updated 2009/11/30
The top part of the preceding figure [figure appears in actual paper] 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 \em downwards\/ has proven vastly more challenging. In particular, with regard to the figure above, consider the following claim: Pm-ttΣkp = Pm+1-ttΣkp ⇒ DIFFm(Σkp) coDIFFm(Σkp) = BH(Σkp). (*) This claim, if true, says that equality translates downwards between levels of the bounded-query hierarchy and the boolean hierarchy levels that (before the fact) are immediately below them. Until recently, it was not known whether (*) \em ever\/ held, except for the degenerate cases m=0 and k=0. Then Hemaspaandra, Hemaspaandra, and Hempel \citehem-hem-hem:j:downward-translation proved that (*) holds for all m, for k > 2. Buhrman and Fortnow~\citebuh-for:j:two-queries 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 \citebuh-for:j:two-queries, our achievement of the k=2 case cannot to 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.