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$ – Joshua Grochow Jul 24 '14 at 0:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.