Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

Paper:

TR05-160 | 10th December 2005 00:00

Dimension Characterizations of Complexity Classes

TR05-160
Authors: Xiaoyang Gu, Jack H. Lutz
Publication: 23rd December 2005 17:49
Downloads: 1592
Keywords:

Abstract:

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.

ISSN 1433-8092 | Imprint