Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > KOLMOGOROV RANDOMNESS:
Reports tagged with kolmogorov randomness:
TR03-040 | 3rd June 2003
Philippe Moser

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

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 ... more >>>




ISSN 1433-8092 | Imprint