ZPP (complexity class)

The complexity class ZPP ( English zero-error probabilistic polynomial time ) contains all problems for which there is a nondeterministic Turing machine that selects from the possible alternatives with the same probability at every point and has the following properties:

• It always returns the correct answer (hence "zero-error" )
• The running time is not limited, but there is a polynomial by which the mean running time is limited

The randomized algorithm is therefore correct, but can sometimes have a much longer running time than in the typical case.

For all problems from ZPP there is also a probabilistic Turing machine that always has a polynomially limited running time, but with a probability of less than 1/2 it does not return an answer instead of the correct answer (ie a “don't know”). The two definitions are therefore equivalent.

ZPP is usually defined as the intersection of RP and co-RP . The problems for which Las Vegas algorithms with mean polynomial running time exist lie in ZPP.

properties

ZPP is completed under complement formation, union and editing. That means that for two languages too . So it is co-ZPP = ZPP. ${\displaystyle L_{1},L_{2}\in {\mathcal {ZPP}}}$ ${\displaystyle L_{1}^{c},L_{1}\cup L_{2},L_{1}\cap L_{2}\in {\mathcal {ZPP}}}$

There is no known ZPP complete problem and there are indications that there are no ZPP complete problems.

Individual evidence

1. ^ Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 195 .
2. ^ Daniel Pierre Bovet and Pierluigi Crescenzi: Introduction to the Theory of Complexity . Prentice Hall, 1994, ISBN 0-13-915380-2 , pp. 198.202 .

Web links

• ZPP . In: Complexity Zoo. (English)