Downward translation (a.k.a. upward separation) refers to cases where the equality of two larger classes implies the equality of two smaller classes. We provide the first unqualified downward translation result completely within the polynomial hierarchy. In particular, we prove that, for k>2, where the "[1]" (respectively,"[2]") denotes that at most one query is (respectively, two queries are) allowed. We also extend this to obtain a more general downward translation result.
展开▼
