Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > ALMOST CLASSES:
Reports tagged with almost classes:
TR05-160 | 10th December 2005
Xiaoyang Gu, Jack H. Lutz

#### Dimension Characterizations of Complexity Classes

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, ... more >>>

ISSN 1433-8092 | Imprint