Notes - Computational Complexity HT25, Randomness

Each non-deterministic transition has two successors, each of which is selected with probability $1/2$. Then

\[\mathbb P(M \text{ accepts }w) = \sum _ {b \text{ accepting branch}} \mathbb P(b) = 2^{-k}\]

where $k$ is the number of branching nodes.

• For each $x \in L$, $M$ accepts with probability $\ge$ $1 - \varepsilon( \vert x \vert )$
• For each $x \notin L$, $M$ rejects with probability $\ge 1 - \varepsilon( \vert x \vert )$

This corresponds to the languages decidable with two-sided error in time $T$, i.e. $L \in \mathsf{BPTIME}(T)$ iff it is recognised by a PTM which correctly accepts with probability $2/3$, and correctly rejects with probability $2/3$ in time $O(T)$.

This corresponds to the languages decidable with one-sided error in time $T$, i.e. $L \in \mathsf{RTIME}(T)$ iff it is recognised by a PTM which correctly accepts with probability $1/2$, and correctly rejects with probability $1$ in time $O(T)$.

“Zero-error probabilistic time” / Las Vegas algorithms

This corresponds to the languages decidable with zero-sided error in time $T$, i.e. $L \in \mathsf{ZPTIME}(T)$ iff it is recognised by a PTM which runs in expected time $O(T(n))$ and $x \in L$ iff the PTM accepts $x$.

“Bounded-error probabilistic polynomial”

This corresponds to the languages decidable with two-sided error in polynomial time (i.e. there exists a PTM which correctly accepts and correctly rejects with probability $2/3$ in both cases).

“Randomised polynomial”

This corresponds to the languages decidable with one-sided error in polynomial time (i.e. there exists a PTM which correctly accepts with probability $1/2$ and correctly rejects with probability $1$).

“Zero-error probabilistic polynomial-time”

This corresponds to the languages decidable with zero-sided error in polynomial time (i.e. the algorithm runs in expected polynomial time and never makes a mistake when it halts).

$L \in \mathsf{BPP}$ iff there exists a polynomial time TM $M$ and a polynomial $p : \mathbb N \to \mathbb N$ such that for every $x \in \{0, 1\}^\ast$,

\[\mathbb P _ {r \in \\{0 ,1\\}^{p(|x|)} } (M(x, r) = L(x)) \ge 2/3\]

where $L(x) = 1$ iff $x \in L$ and $r$ is chosen randomly (this can be seen as also referring to the proportion of accepting/rejecting paths).

$L \in \mathsf{RP}$ iff there exists a polynomial time TM $M$ and a polynomial $p : \mathbb N \to \mathbb N$ such that for every $x \in L$,

\[\mathbb P _ {r \in \\{0 ,1\\}^{p(|x|)} } (M(x, r) = 1) \ge 1/2\]

and for every $x \notin L$,

\[\mathbb P _ {r \in \\{0 ,1\\}^{p(|x|)} } (M(x, r) = 1) = 0\]

where $L(x) = 1$ iff $x \in L$ and $r$ is chosen randomly (this can be seen as also referring to the proportion of accepting/rejecting paths).

The following are equivalent for any language $L$:

• $L \in \mathsf{BPP}$
• $L$ is decided by a probabilistic polynomial-time machine with two-sided error $1/2 - 1/\text{poly}( \vert x \vert )$.
• $L$ is decided by a probabilistic polynomial-time machine with two-sided error $1/2^{\text{poly}( \vert x \vert )}$.

(2) implies (3):

Suppose $M$ is the PTM such that for every $x \in \{0, 1\}^\ast$, $\mathbb P[M(x) = L(x)] \ge \frac 1 2 + \vert x \vert ^{-c}$. Consider the PTM $M$ which on input $x$, runs $M(x)$ for $k = 8 \vert x \vert ^{2c + d}$ times, obtaining $k$ outputs $y _ 1, \ldots, y _ k \in {0, 1}$. If the majority of the outputs is $1$, then output $1$; otherwise output $0$.

To analyse this machine, define for every $1 \le i \le k$ the random variable $X _ i$ to equal $1$ if $y _ i = L(x)$ and to equal $0$ otherwise. Note that $X _ 1, \ldots, X _ k$ are independent Boolean random variables with $\mathbb E[X _ i] = \mathbb P[X _ i = 1] \ge p$ for $p = 1/2 + \vert x \vert ^{-c}$.

Then the Chernoff bound implies that for $\delta$ sufficiently small,

\[\mathbb P\left[ |\sum^k _ {i = 1} X _ i - pk]| > \delta pk \right] < e^{-\frac{\delta^2}{4}pk}\]

In our case, $p = \frac 1 2 + \vert x \vert ^{-c}$, and setting $\delta = \vert x \vert ^{-c} / 2$ guarantees that if $\sum^k _ {i=1} X _ i \ge pk - \delta pk$ then we will output the right answer. Hence the probability we output a wrong answer is bounded by

\[\begin{aligned} e^{-\frac{1}{4|x|^{2c} } \frac{1}{2} 8|x|^{2c + d} } &\le 2^{-|x|^d} \\\\ &= 1/2^{\text{poly}(|x|)} \end{aligned}\]

Other directions: @todo

The following are equivalent for any language $L$:

• $L \in \mathsf{RP}$
• $L$ is decided by a probabilistic polynomial-time machine with one-sided error $1/2 - 1/\text{poly}( \vert x \vert )$.
• $L$ is decided by a probabilistic polynomial-time machine with one-sided error $1/2^{\text{poly}( \vert x \vert )}$.

@todo

1. $\mathsf{P} \stackrel{(1)}\subseteq \mathsf{ZPP} \stackrel{(2)}\subseteq \mathsf{RP} \stackrel{(3)}\subseteq \mathsf{NP} \stackrel{(4)}\subseteq \mathsf{PSPACE}$
   1. This inclusion follows from the fact that any polynomial-time deterministic Turing machine definitely halts within a polynomial number of steps.
   2. We can modify the PTM deciding a $\mathsf{ZPP}$ language to reject when it doesn’t halt within the given time bound, giving a Turing machine deciding the language with a one sided error.
   3. This follows from the characterisation of $\mathsf{RP}$ as the set of languages where there exists a TM $M(x, r)$ if $x \in L$, then at least half of the computation paths $r$ accept, and if $x \notin L$, then no paths accept. The existence of $M$ also then establishes that $L \in \mathsf{NP}$.
   4. This follows from the theorem establishing that $\mathsf{NTIME}(T)$ can be simulated in $\mathsf{DSPACE}(T)$.
2. This would be trivial if $\mathsf{RP}$ was defined in terms of having a probability of success of $2/3$ rather than just $1/2$. But since the error can be reduced for any $\mathsf{RP}$ language with only a polynomial slowdown, the inclusion follows by reducing the error to $1/2$.
3. To decide if $L \in \mathsf{BPP}$ is in $\mathsf{PSPACE}$, we can exhaustively enumerate over all computation paths and accept if and only if the probability of acceptance is at least $1/2$. This can be done in polynomial space.

Suppose that $L \in \mathsf{BPP}$. Then by the witness characterisation of $\mathsf{BPP}$, i.e.

$L \in \mathsf{BPP}$ iff there exists a polynomial time TM $M$ and a polynomial $p : \mathbb N \to \mathbb N$ such that for every $x \in \{0, 1\}^\ast$,

\[> \mathbb P _ {r \in \\{0 ,1\\}^{p(|x|)} } (M(x, r) = L(x)) \ge 2/3 >\]

where $L(x) = 1$ iff $x \in L$ and $r$ is chosen randomly (this can be seen as also referring to the proportion of accepting/rejecting paths).

together with the error reduction result that

The following are equivalent:

1. $L \in \mathsf{RP}$
2. $L$ is decided by a probabilistic polynomial-time machine with one-sided error $1/2 - 1/\text{poly}( \vert x \vert )$.
3. $L$ is decided by a probabilistic polynomial-time machine with one-sided error $1/2^{\text{poly}( \vert x \vert )}$.

It follows that there exists a TM $M$ that on inputs of size $n$ uses $m = \text{poly}( \vert x \vert )$ random bits and such that for every $x \in \{0, 1\}^n$, $\mathbb P _ {r \in \{0, 1\}^m } [M(x, r) \ne L(x)] \le 2^{-n-1}$.

Call a string $r \in \{0, 1\}^m$ bad if on input $x \in \{0, 1\}^n$, $M(x, r) \ne L(x)$, and otherwise call $r$ good on $x$.

For every $x$, at most $\frac{2^m}{2^{n+1}}$ strings $r$ are bad for $x$. Adding over all $x \in \{0, 1\}^n$, there are at most $2^n \cdot \frac{2^m}{2^{n+1} } = 2^m / 2$ strings $r$ that are bad for some $x$.

Hence, there exists a string $r _ 0 \in \{0, 1\}^m$ that is good for every $x \in \{0, 1\}^n$. We can hardwire such a string $r _ 0$ to obtain a circuit $C$ that on input $x$ outputs $M(x, r _ 0)$. The circuit $C$ will satisfy $C(x) = L(x)$ for every $x \in \{0, 1\}^n$, as required.