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:
“Parents have railed against shelters near schools, but no one has made any connection between the crazed consumerism of our kids and their elders’ cold unconcern toward others. Maybe the homeless are not the only ones who need to spend time in these places to thaw out.”
—Anna Quindlen (b. 1952)
“When we of the so-called better classes are scared as men were never scared in history at material ugliness and hardship; when we put off marriage until our house can be artistic, and quake at the thought of having a child without a bank-account and doomed to manual labor, it is time for thinking men to protest against so unmanly and irreligious a state of opinion.”
—William James (1842–1910)