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 to, connection and/or classes:
“One must always maintain one’s connection to the past and yet ceaselessly pull away from it. To remain in touch with the past requires a love of memory. To remain in touch with the past requires a constant imaginative effort.”
—Gaston Bachelard (1884–1962)
“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)
“I have no doubt but that the misery of the lower classes will be found to abate whenever the Government assumes a freer aspect and the laws favor a subdivision of Property.”
—James Madison (1751–1836)