1999/10/01 by Edith Hemaspaandra, Hemaspaandra, Edith, Lane A. Hemaspaandra +4 · 1 citation
Computer Science · #Advanced Graph Theory Research #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #Formal Methods in Verification #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/9910008
13 pages, an extended abstract was presented at the 16th Symposium on Theoretical Aspects of Computer Science
openalex publication_date 1999/10/01 · arxiv created 1999/10/04 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Downward translation of equality refers to cases where a collapse of some pair of complexity classes would induce a collapse of some other pair of complexity classes that (a priori) one expects are smaller. Recently, the first downward translation of equality was obtained that applied to the polynomial hierarchy-in particular, to bounded access to its levels [cs.CC/9910007]. In this paper, we provide a much broader downward translation that extends not only that downward translation but also that translation's elegant enhancement by Buhrman and Fortnow. Our work also sheds light on previous research on the structure of refined polynomial hierarchies, and strengthens the connection between the collapse of bounded query hierarchies and the collapse of the polynomial hierarchy.