Definition. Probabilistic Turing machine [prob-turing-machine]

A computation model that begins with a tree. When you reach a branch, you flip a coin!

We can define complexity classes based on the probability of reaching accept/reject leaves.

Definition 1. Randomized Polynomial Time [RP]

The following are equivalent:

$L \in \text{RP}$ (Randomized Polytime) if there is a probabilistic Turing machine that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ , and has a greater than or equal to 50% chance of reaching an accepting leaf.
- $L \notin \text{RP}$ if the probabilistic Turing machine has a 0% chance of reaching an accepting leaf. (must reach reject state)
Algorithm’s Output Accept Reject

Correct Output

Accept $\geq 50\%$ / true positive $\leq 50\%$ / false negative

Reject 0 / false positive 1 / true negative
$L \in \text{RP}$ if there is a PTM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior:
- $x \in L$ : $\text{Pr}\left( \text{accept} \right) \geq 50\%$
- $x \notin L$ : $\text{Pr}\left( \text{reject} \right) = 100\%$
$L \in \text{RP}$ if there exists a deterministic polytime TM V such that:
- $x \in L$ : for at least half of all $y$ with $|y| = \text{poly}\left( |x| \right)$ , $V\ \text{accepts}\ \left( {x,y} \right)$
- $x \notin L$ : for all y with $|y| = \text{poly}\left( |x| \right)$ , $V\ \text{rejects}\ \left( {x,y} \right)$

Question. Why is RP useful?

Answer. Because we can build things that compute in RP, but we cannot easily simulate NP.

…useful picture…

If there was an NP-complete language in RP, then RP would equal NP.

$L \in \text{NP}$ if there is a TM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior: $\text{Pr}\left( \text{reaching accept} \right) > 0$

Definition. co-RP

$L \in \text{coRP}$ if there is a PTM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ , and has the following behavior:

$x \in L$ (strings in the language) have a 100% chance of being accepted
$x \notin L$ have at least or equal to 50% chance of being rejected

Example. A Probabilistic Puzzle

Let $a = \left\lbrack {a_{1},a_{2},a_{3},\ldots a_{n}} \right\rbrack$ be a vector of $n$ bits.

There are two possibilities:

$a$ is all zeros
exactly half of $a$ are zeros

Question. How many bits must you look at to tell?

Answer.

Non-probabilistically: n/2 + 1
Probabilistically: just one!

Definition 2. Bounded-error Probabilistic Polynomial Time [BPP]

$L \in \text{BPP}$ (Bounded-error Probabilistic Polytime) if there is a probabilistic Turing machine that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior:

$x \in L$ if the probability of accepting is greater than $\frac{2}{3}$
$x \in L$ if the probability of rejecting is greater than $\frac{2}{3}$
( $\frac{2}{3}$ is arbitrary: we just need $\frac{p}{q} > \frac{1}{2}$ )

Correct Output / Algorithm’s Output	Accept	Reject
Accept	$\geq \frac{2}{3}$ / true positive	$\leq \frac{1}{3}$ / false negative
Reject	$\leq \frac{1}{3}$ / false positive	$\geq \frac{2}{3}$ / true negative

…helpful diagram…

Definition 3. Amplification [amplification]

Modifying the definition of $\text{RP}$ a little bit: $L \in \text{RP}(p)$ if there is a PTM that, on input $x$ , runs in time $\text{poly}\left( |x| \right)$ and has behavior:

$\text{Pr}\left( \text{reaching accept} \right) \geq p$
$\text{Pr}\left( \text{reaching reject} \right) = 1$

Example. Claim: $\text{RP}\left( \frac{1}{2} \right) = \text{RP}\left( \frac{3}{4} \right)$

Proof.

Let $L \in \text{RP}\left( \frac{1}{2} \right)$ . There exists PTM $M$ such that $x \in L:P\left( {M\ \text{accept}\ x} \right) \geq \frac{1}{2}$ , $x \notin L:\text{Pr}\left( {M\ \text{rejects}\ x} \right) = 1$ .

Let $N$ be the Turing machine on input $x$

Run $M$ on input $x$
Run $M$ on input $x$
if either accepted, then accept
else reject

	Algorithm’s Output	Accept	Reject
Correct Output
Accept		$\geq 50\%$ / true positive	$\leq 50\%$ / false negative
Reject		0 / false positive	1 / true negative