Moser, Philippe (2003) RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP. Technical Report. Electronic Colloquium on Computational Complexity.
|
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 |
| 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