ZPP (complexity) - Connection To Other Classes

Connection To Other Classes

Since ZPP = RPcoRP, 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 PZPP, as PEXPTIME (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 dress and war is not far to seek; your finest clothes are those you wear as soldiers.
    Virginia Woolf (1882–1941)

    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)