We use derandomization to show that sequences of positive pspace-dimension - in fact, even positive Δ_k~p-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 Δ_3~p-dimension is positive, then BPP is contained in 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 dimension-almost-class of a complexity class C, denoted by dimalmost-C, is the class consisting of all problems A such that A ∈ 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-Sep = dimalmost-P-Sep, in which even the almost-class appears to be a new characterization.
展开▼
