Share and Export
Share and Export
Impagliazzo, Russell and Moser, Philippe (2009) A zero-one law for RP and derandomization of AM if NP is not small. Information and Computation, 207 (7). pp. 787-792. ISSN 0890-5401
Preview
PM-Zero-2009.pdf
Download (336kB) | Preview
Abstract
We show that if RP does not have p-measure zero then ZPP = EXP. As corollaries we obtain a zero-one law for RP in EXP, and that both probabilistic classes ZPP and RP have the same measure in EXP. We also prove that if NP does not have p-measure zero then NP = AM.
| Item Type: | Article |
|---|---|
| Additional Information: | This is the preprint version of the published article, which is available at DOI: 10.1016/j.ic.2009.02.002 |
| Keywords: | Resource-bounded measure; Derandomization; |
| Academic Unit: | Faculty of Science and Engineering > Computer Science |
| Item ID: | 8245 |
| Identification Number: | 10.1016/j.ic.2009.02.002 |
| Depositing User: | Philippe Moser |
| Date Deposited: | 29 May 2017 14:34 |
| Journal or Publication Title: | Information and Computation |
| Publisher: | Elsevier |
| Refereed: | No |
| Related URLs: | |
| URI: | https://mural.maynoothuniversity.ie/id/eprint/8245 |
| 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
