Article ID Journal Published Year Pages File Type
426668 Information and Computation 2009 6 Pages PDF
Abstract

We show that if RP does not have p-measure zero then ZPP = EXP. As corollaries we obtain a zero-one law for RP in EXP, and that both probabilistic classes ZPP and RP have the same measure in EXP. We also prove that if NP does not have p-measure zero then NP = AM.

Related Topics
Physical Sciences and Engineering Computer Science Computational Theory and Mathematics