A zero-one SUBEXP-dimension law for BPP

Share and Export

Moser, Philippe (2011) A zero-one SUBEXP-dimension law for BPP. Information Processing Letters, 111 (9). pp. 429-432. ISSN 0020-0190

PDF
Available under License Creative Commons Attribution Non-commercial Share Alike.
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
Related URLs:	http://www.journals.elsevier.com/informa...
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