Connection To Other Classes
Since ZPP = RP ∩ coRP, ZPP is obviously contained in both RP and coRP.
The class P is contained in ZPP, and some computer scientists have conjectured that P = ZPP, i.e., every Las Vegas algorithm has a deterministic polynomial-time equivalent.
A proof for ZPP = EXPTIME (though that is almost certainly false) would imply that P ≠ ZPP, as P ≠ EXPTIME (see time hierarchy theorem).
Read more about this topic: ZPP (complexity)
Famous quotes containing the words connection and/or classes:
“The connection between our knowledge and the abyss of being is still real, and the explication must be not less magnificent.”
—Ralph Waldo Emerson (1803–1882)
“One marvels why ... the middle classes still insist on so much discomfort for their children at such expense to themselves.”
—E.M. (Edward Morgan)