Randomized algorithm

A randomized algorithm makes some choices using random bits.

A probabilistic Turing machine is a Turing machine whose transitions may depend on independent random bits.

A randomized decision algorithm has one-sided error when one answer is always correct and only the other answer can be mistaken.

$\mathbf{RP}$ contains decision problems with a polynomial-time randomized algorithm that rejects every negative instance and accepts every positive instance with probability at least one half.

$\mathbf{co}\text{-}\mathbf{RP}$ consists of complements of languages in RP. Its algorithms always accept positive instances and reject negative instances with probability at least one half.

$\mathbf{ZPP}=\mathbf{RP}\cap \mathbf{co}\text{-}\mathbf{RP}$. Equivalently, it consists of problems having an always-correct randomized algorithm with polynomial expected running time.

Independent repetitions reduce a randomized algorithm's error probability while preserving polynomial running time.

Polynomial identity testing asks whether a polynomial represented implicitly, such as by an arithmetic circuit or a remainder computation, is the zero polynomial.