In 1986 during the prehistory of Hardness vs. Randomness, Sipser showed that if time does not have nontrivial space simulations one can derandomize. Given a (later-proved) assumption about extractor constructions If there is a constant c such that DTIME(2

Later results used hardness against nonuniform circuits to derandomize complexity classes. For example Impagliazzo and Wigderson show^{cn}) is not contained in DSPACE(2^{.99cn}) then P=RP.If E does not have circuits of size 2

where E=DTIME(2^{o(n)}then P=BPP.^{O(n)}).I recently discovered that Peter Bro Miltersen in his derandomization survey (page 56) notes that you can use a uniform assumption, a weaker version of Sipser's assumption.

If E is not contained is DSPACE(2

Miltersen's proof works by searching all circuits, using the local checkability of E to verify the correctness of the circuit.^{o(n)}) then E does not have circuits of size 2^{o(n)}and thus P=BPP.You can even assume the circuits have access to QBF or Σ

_{2}^{p}gates, the later an assumption we needed in a recent paper. Saying E is not contained in subexponential space is so much nicer than saying E does not have nonuniform subexponential-size circuits with Σ_{2}^{p}gates.Technical Note: For all of the above you need to assume the separations at all input lengths.

--

Posted by Lance to Computational Complexity at 3/30/2006 07:34:00 PM