ZPP (complexity)

The complexity class ZPP ( zero -error probabilistic polynomial english time) includes all the problems for which there is a non-deterministic Turing machine that selects at each location with equal probability among the possible alternatives and has the following properties:

• You are always the right answer back (hence "zero -error " )
• The term is not limited, however, there exists a polynomial by which the average running time is limited

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

For all the problems of ZPP also exists a probabilistic Turing machine that always has a polynomial of limited duration, but with smaller probability 1/2 instead of the correct answer no response (ie, a "do not know " ) returns. The two definitions are equivalent.

Defines ZPP is usually to be the intersection of RP and co -RP. Those problems for which there are Las Vegas algorithms with medium polynomial running time, are ZPP.

Properties

ZPP is closed under complementation, union and intersection. This means that for two languages ​​as well. It is co- ZPP = ZPP.

There is no known ZPP -complete problem, and there is evidence that there is no CPP -complete problems.