pith. sign in

arxiv: cs/9910008 · v2 · submitted 1999-10-01 · 💻 cs.CC

Translating Equality Downwards

classification 💻 cs.CC
keywords translationcollapsedownwardequalitypolynomialboundedclassescomplexity
0
0 comments X
read the original abstract

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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.