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