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)
“We will have to give up the hope that, if we try hard, we somehow will always do right by our children. The connection is imperfect. We will sometimes do wrong.”
—Judith Viorst (20th century)
“Genocide begins, however improbably, in the conviction that classes of biological distinction indisputably sanction social and political discrimination.”
—Andrea Dworkin (b. 1946)