Editing ZPP (complexity) (section)

== Intersection definition ==
The class '''ZPP''' is exactly equal to the intersection of the classes '''[[RP (complexity)|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, run A on the input for one step. If it returns YES, the answer must be YES. Otherwise, run B on the input for one step. 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 ''k''th round shrinks exponentially in ''k'', showing that the [[expected value|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|Markov's Inequality]], the chance that it will yield an answer before we stop it is at least 1/2. This means the chance we'll give the wrong answer on a YES instance, by stopping and yielding NO, is at most 1/2, fitting the definition of an '''RP''' algorithm. The '''co-RP''' algorithm is identical, except that it gives YES if C "times out".