Intersection Definition
The class ZPP is exactly equal to the intersection of the classes RP and Co-RP. This is often taken to be the definition of ZPP. To show this, first note that every problem which is in both RP and co-RP has a Las Vegas algorithm as follows:
- Suppose we have a language L recognized by both the RP algorithm A and the (possibly completely different) co-RP algorithm B.
- Given an input in L, run A on the input. If it returns YES, the answer must be YES. Otherwise, run B on the input. If it returns NO, the answer must be NO. If neither occurs, repeat this step.
Note that only one machine can ever give a wrong answer, and the chance of that machine giving the wrong answer during each repetition is at most 50%. This means that the chance of reaching the kth round shrinks exponentially in k, showing that the expected running time is polynomial. This shows that RP intersect co-RP is contained in ZPP.
To show that ZPP is contained in RP intersect co-RP, suppose we have a Las Vegas algorithm C to solve a problem. We can then construct the following RP algorithm:
- Run C for at least double its expected running time. If it gives an answer, give that answer. If it doesn't give any answer before we stop it, give NO.
By Markov's Inequality, the chance that it will yield an answer before we stop it is 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is only 1/2, fitting the definition of an RP algorithm. The co-RP algorithm is identical, except that it gives YES if C "times out".
Read more about this topic: ZPP (complexity)
Famous quotes containing the words intersection and/or definition:
“You can always tell a Midwestern couple in Europe because they will be standing in the middle of a busy intersection looking at a wind-blown map and arguing over which way is west. European cities, with their wandering streets and undisciplined alleys, drive Midwesterners practically insane.”
—Bill Bryson (b. 1951)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)