If there is a constant c such that DTIME(2Later 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 2where 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(2Miltersen'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.

Lance,

ReplyDeleteWhat happened to NC and the complexity theory as viewed with the parallelization glasses? Is someone doing tangible research with it? Would like to know.

Thanks a lot!

Amar