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
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: |
https://doi.org/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 |
| 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 per month over past year
Origin of downloads
Altmetric
Altmetric