Definition. Randomized Polynomial Time [RP]

The following are equivalent:

1. $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

2. $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\%$

3. $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)$

…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