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:
“It may comfort you to know that if your child reaches the age of eleven or twelve and you have a good bond or relationship, no matter how dramatic adolescence becomes, you children will probably turn out all right and want some form of connection to you in adulthood.”
—Charlotte Davis Kasl (20th century)
“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 am ... by tradition and long study a complete snob. P. Marlowe and I do not despise the upper classes because they take baths and have money; we despise them because they are phony.”
—Raymond Chandler (1888–1959)