Do padding arguments exist for probabilistic classes? For example, would $P=BPP\Rightarrow EXP=BPEXP$? What about for space bounded computation? Would constant space derandomization imply $L=RL$ or $L=BPL$?

  • 4
    $\begingroup$ Yes, of course. Padding just changes the input size, and hence changes how you express (e.g.) the running time as a function of input size. What do you mean by "constant space derandomization"? If you mean $\mathsf{BPSPACE}(O(1))$, this is the same as the class of regular languages.... $\endgroup$ Jul 24, 2014 at 0:13


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.