|
Abstract : |
We prove that if BPP 6 = EXP, then every problem in BPP can be solved deterministically in subexponential time on almost every input ( on every samplable ensemble for infinitely many input sizes). This is the first derandomization result for BPP based on uniform, noncryptographic hardness assumptions. It implies the following gap in the average-instance complexities of problems in BPP: either these complexities are always sub-exponential or they contain arbitrarily large exponential functions. We use a construction of a small "pseudorandom " set of strings from a "hard function" in EXP which is identical to that used in the, |
