Moser, Philippe (2011) A zero-one SUBEXP-dimension law for BPP. Information Processing Letters, 111 (9). pp. 429-432. ISSN 0020-0190
![[img]](https://mural.maynoothuniversity.ie/style/images/fileicons/application_pdf.png) |
Download (130kB)
|
Abstract
We show that BPP has either SUBEXP-dimension zero (randomness is easy) or BPP = EXP (randomness is intractable).
| Item Type: | Article |
|---|---|
| Additional Information: | Preprint version of original published article. The definitive version of this article is available at Information Processing Letters (2011) Vol.111 No.9, pp.429–432. DOI: http://dx.doi.org/10.1016/j.ipl.2011.01.019 |
| Keywords: | zero-one; SUBEXP-dimension law; BPP; |
| Academic Unit: | Faculty of Science and Engineering > Chemistry |
| Item ID: | 3838 |
| Depositing User: | Philippe Moser |
| Date Deposited: | 04 Sep 2012 14:35 |
| Journal or Publication Title: | Information Processing Letters |
| Publisher: | Elsevier |
| Refereed: | Yes |
| URI: | |
| Use Licence: | This item is available under a Creative Commons Attribution Non Commercial Share Alike Licence (CC BY-NC-SA). Details of this licence are available here |
Repository Staff Only(login required)
 |
Item control page |
Downloads
Downloads per month over past year
Altmetric
Altmetric