Share and Export
Share and Export
Moser, Philippe (2003) RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP. Technical Report. Electronic Colloquium on Computational Complexity.
Preview
Available under License Creative Commons Attribution Non-commercial Share Alike.
Download (214kB) | Preview
Official URL: https://eccc.weizmann.ac.il/report/2003/040/
Abstract
We use recent results on the hardness of resource-bounded
Kolmogorov random strings, to prove that RP is small in SUBEXP
else ZPP=PSPACE and NP=EXP.
We also prove that if NP is not small in SUBEXP, then
NP=AM, improving a former result which held for the measure on E.
| Item Type: | Monograph (Technical Report) |
|---|---|
| Keywords: | kolmogorov randomness; Resource-bounded measure; |
| Academic Unit: | Faculty of Science and Engineering > Computer Science |
| Item ID: | 10310 |
| Identification Number: | TR03-040 |
| Depositing User: | Philippe Moser |
| Date Deposited: | 11 Dec 2018 16:42 |
| Publisher: | Electronic Colloquium on Computational Complexity |
| 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 |
Downloads
Downloads per month over past year
Origin of downloads
Altmetric Badge
Repository Staff Only (login required)
- Item control page
