Probabilistic polynomial-time Turing machines

A probabilistic Turing machine is a deterministic multitape Turing machine equipped with an additional read-only tape of random bits. On input $x$ and random string $r$, it follows the deterministic computation determined by $(x,r)$.

Such a machine runs in probabilistic polynomial time when there is a polynomial $p$ such that, on every input of length $n$, it halts within $p(n)$ steps after reading at most $p(n)$ random bits. Fixing one such bound, the computation on $x$ is viewed as a deterministic computation on $(x,r)$ for $r\in \{0,1{\}}^{p(\mathrm{\mid }x\mathrm{\mid })}$; any unread suffix of $r$ is ignored.

For a fixed input $x$, the machine's acceptance probability is ${\mathbb{P}}_r(M(x,r)\text{ accepts})=\frac{\mathrm{\mid }\{r\in \{0,1{\}}^{p(\mathrm{\mid }x\mathrm{\mid })}:M(x,r)\text{ accepts}\}\mathrm{\mid }}{2^{p(\mathrm{\mid }x\mathrm{\mid })}}\mathrm{.}$ This value does not depend on the chosen valid bound: replacing $p(\mathrm{\mid }x\mathrm{\mid })$ by a larger length merely gives every relevant random prefix the same number of extensions.

• A probabilistic machine is still an ordinary deterministic machine after the random string is fixed.
• The runtime bound is worst-case over the random string as well as over the input.