ZPP

This is an article about a computational complexity class. For Polish communist political organisation, see Związek Patriotów Polskich. 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 unbounded, but is polynomial on average for any input. In other words, the algorithm is allowed to flip a trul ...