TR05-160 Authors: Xiaoyang Gu, Jack H. Lutz

Publication: 23rd December 2005 17:49

Downloads: 1592

Keywords:

We use derandomization to show that sequences of positive $\pspace$-dimension -- in fact, even positive $\Delta^\p_k$-dimension

for suitable $k$ -- have, for many purposes, the full power of random oracles. For example, we show that, if $S$ is any binary sequence whose $\Delta^p_3$-dimension is positive, then $\BPP\subseteq \P^S$ and, moreover, every $\BPP$ promise problem is $\P^S$-separable. We prove analogous results at higher levels of the polynomial-time hierarchy.

The {\em dimension-almost-class} of a complexity class $\mathcal{C}$, denoted by $\dimalmost\mathcal{C}$, is the class consisting of all problems $A$ such that $A\in\mathcal{C}^S$ for all but a Hausdorff dimension $0$ set of oracles $S$. Our results yield several

characterizations of complexity classes,

such as $\BPP=\dimalmost\P$ and $\AM =\dimalmost\NP$, that refine previously known results on almost-classes. They also yield results, such as $\promise\BPP=\almost\P\text{-}\sep=\dimalmost\P\text{-}\sep$,

in which even the almost-class appears to be a new characterization.