##### Wikipedia

**ZPP (complexity)**

In complexity theory, **ZPP** (zero-error probabilistic polynomial time) is the complexity class of problems for which a probabilistic Turing machine exists with these properties:

- It always returns the correct YES or NO answer.
- The running time is polynomial in expectation for every input.

In other words, if the algorithm is allowed to flip a truly-random coin while it is running, it will always return the correct answer and, for a problem of size *n*, there is some polynomial *p*(*n*) such that the average running time will be less than *p*(*n*), even though it might occasionally be much longer. Such an algorithm is called a Las Vegas algorithm.

Alternatively, **ZPP** can be defined as the class of problems for which a probabilistic Turing machine exists with these properties:

- It always runs in polynomial time.
- It returns an answer YES, NO or DO NOT KNOW.
- The answer is always either DO NOT KNOW or the correct answer.
- It returns DO NOT KNOW with probability at most 1/2 (and the correct answer otherwise).

The two definitions are equivalent.

The definition of **ZPP** is based on probabilistic Turing machines, but, for clarity, note that other complexity classes based on them include ** BPP** and ** RP**. The class ** BQP** is based on another machine with randomness: the quantum computer.

**ZPP**

**ZPP** may refer to:

- ZPP (complexity), zero-error probabilistic polynomial time
- Zinc protoporphyrin
- zirconium-potassium perchlorate, a pyrotechnic composition
- Związek Patriotów Polskich, a Polish communist political party

**zpp** may refer to:

- ISO 639:zpp, ISO 639-3 code for El Alto Zapotec