Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR03-040 | 3rd June 2003 00:00

RP is Small in SUBEXP else ZPP equals PSPACE and NP equals EXP

RSS-Feed




TR03-040
Authors: Philippe Moser
Publication: 6th June 2003 19:28
Downloads: 908
Keywords: 


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.



ISSN 1433-8092 | Imprint