| Article ID | Journal | Published Year | Pages | File Type |
|---|---|---|---|---|
| 428635 | Information Processing Letters | 2011 | 4 Pages |
Abstract
We show that BPPBPP has either SUBEXPSUBEXP-dimension zero (randomness is easy) or BPP=EXPBPP=EXP (randomness is intractable).
Research highlights► We show that BPPBPP has either SUBEXPSUBEXP-dimension zero (randomness is easy) or BPP=EXPBPP=EXP (randomness is intractable). ► This paper improves Melkebeek's zero-one law for BPP by strengthening the statement “randomness is easy” in two aspects. ► First by reducing the time-bounds of the martingales from polynomial to subpolynomial. ► Second by replacing measure with dimension.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Philippe Moser,