Computational Complexity HT25, Randomness and probabilistic computation

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 greater than or equal to $2/3$, and correctly rejects with probability $2/3$ in time $O(T)$.

• $\mathbb P(M(x) = L(x)) \ge \frac 2 3$

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 greater than or equal to $1/2$, and correctly rejects with probability $1$ in time $O(T)$.

• $P(M(x) = 1 \mid x \in L) \ge 1/2$
• $P(M(x) = 0 \mid x \notin L) = 1$

“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 greater than or equal to $2/3$ in both cases).

• $\mathbb P(M(x) = L(x)) \ge \frac 2 3$

“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 greater than or equal to $1/2$ and correctly rejects with probability $1$).

• $P(M(x) = 1 \mid x \in L) \ge 1/2$
• $P(M(x) = 0 \mid x \notin L) = 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).

WalkSAT.

Randomised polynomial zero testing.

$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 \lbrace 0, 1\rbrace^\ast$,

\[\mathbb P _ {r \in \lbrace 0 ,1\rbrace^{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 \lbrace 0 ,1\rbrace^{p(|x|)} } (M(x, r) = 1) \ge 1/2\]

and for every $x \notin L$,

\[\mathbb P _ {r \in \lbrace 0 ,1\rbrace^{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).

A language $L$ is in $\mathsf{ZPP}$ iff there exists a polynomial-time PTM $M$ with outputs in $\lbrace 0, 1, \square \rbrace$ such that for every $x \in \lbrace 0, 1 \rbrace^\ast$, with probability $1$, $M(x) \in \lbrace L(x), \square \rbrace$ and $\mathbb P[M(x) = \square] \le 1/2$.

---

Given a PTM with zero-sided error, modify it so that if it’s taking too long, it just outputs $\square$ instead.

Given a machine as above with outputs in $\lbrace 0, 1, \square \rbrace$, modify it so that if it outputs $\square$, it just tries again. Eventually it will output $0$ or $1$, and does so in expected polynomial time.

Suppose:

• $X _ 1, \ldots, X _ k$ are mutually independent random variables over $\lbrace 0, 1 \rbrace$
• $\mu = \sum^k _ {i=1} \mathbb E[X _ i]$

Then for every $0 < \varepsilon < 1$:

• $\mathbb P[\sum^k _ {i = 1} X _ i \le (1 - \varepsilon)\mu] \le e^{\frac{-\varepsilon^2 \mu}{2} }$

---

This is useful because if $X _ i$ is the random variable representing whether run $i$ of a randomised algorithm with two sided error was successful, say $M _ i(x) = L(x)$, then the probability that a majority vote on those $X _ i$ fails is given by

\[\mathbb P\left[\sum^k_{i=1} X_i \le \frac{k}{2}\right] \le \mathbb P\left[\sum^k_{i=1} X_i \le (1 - \varepsilon)\mu\right] \le e^{ \frac{-\varepsilon^2 \mu}{2} }\]

where you pick a convenient value of $\varepsilon$.

The following are equivalent for any language $L$:

1. $L \in \mathsf{BPP}$ (i.e. there is some polynomial-time PTM with two-sided error at most $1/3$).
2. For any $c > 0$, $L$ is decided by a polynomial-time PTM with two-sided error at most $1/2 - n^{-c}$.
3. For any $d > 0$, $L$ is decided by a polynomial-time PTM with two-sided error at most $2^{-n^d}$.

(1) implies (2):

If $L \in \mathsf{BPP}$, then $L$ is decided by a PTM with two-sided error less than $1/3$, which is stronger than two-sided error less than $1/2 - 1/\text{poly}( \vert x \vert )$ for $ \vert x \vert $ sufficiently large. If $ \vert x \vert $ is not large enough, we can hard code those inputs.

---

(2) implies (3):

Suppose $M$ is the PTM such that for every $x \in \lbrace 0, 1\rbrace^\ast$, $\mathbb P[M(x) = L(x)] \ge \frac 1 2 + \vert x \vert ^{-c}$ (a bound on the two sided error).

Consider the PTM $N$ which on input $x$, runs $M(x)$ a number of $k$ 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}$.

The Chernoff bound implies that for $0 < \delta < 1$,

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

Our goal is to bound the probability that $\sum^k _ {i = 1} X _ i < k/2$, i.e. the majority vote fails. In our case, $p = \frac 1 2 + \vert x \vert ^{-c}$. Note that if we set $\delta = \vert x \vert ^{-c} / 2$ (which satisfies $0 < \delta < 1$), then

\[\begin{aligned} pk - \delta pk &= \left(\frac 1 2 + |x|^{-c}\right)k - \frac{|x|^{-c} }{2}\left(\frac 1 2 + |x|^{-c}\right) k \\\\ &= \frac k 2 + |x|^{-c} k - \frac{|x|^{-c} }{4}k - \frac{|x|^{-2c} }{2}k \\\\ &= \frac k 2 + \frac{|x|^{-c} }{2} k \\\\ &\ge \frac k 2 \end{aligned}\]

and thus if $\sum _ {i=1}^k X _ i < \frac k 2$, then automatically $\sum^k _ {i=1} X _ i < pk - \delta pk$. Therefore

\[\mathbb P\left[ \sum^k_{i=1} X_i < \frac{k}{2} \right] \le \mathbb P\left[ \sum^k _ {i = 1} X _ i < pk - \delta pk \right] \le e^{-\frac{\delta^2 pk}{2} } = e^{-\frac{\left(\frac{|x|^{-c} }{2}\right)^2\left(\frac 1 2 + |x|^{-c}\right)k}{2} }\]

Hence if we set $k = 8 \vert x \vert ^{2c + d} \lceil 2\ln 2 \rceil$, we obtain

\[\begin{aligned} e^{-\frac{\delta^2}{2}pk} &= e^{-\frac{\left(\frac{|x|^{-c} }{2}\right)^2\left(\frac 1 2 + |x|^{-c}\right)\left(8|x|^{2c + d} \lceil 2\ln 2 \rceil\right)}{2} } \\\\ &= e^{-\left(\frac 1 2 + |x|^{-c}\right) \cdot \frac{|x|^{2c + d} }{|x|^{2c} } \lceil 2\ln 2 \rceil} \\\\ &\le e^{-\ln 2 |x|^d} \\\\ &= 2^{-|x|^d} \end{aligned}\]

Overall

\[\mathbb P\left[ \sum^k_{i=1} X_i < \frac{k}{2} \right] \le 2^{-|x|^d}\]

as required.

(Why not solve for $\delta$ in $k/2 = pk - \delta pk$ and use this value in the Chernoff bound instead? This is possible, but taking $\delta = \vert x \vert ^{-c}/2$ gives a simpler expression and means it’s easier to spot a $k$ such that the bound works as desired).

---

(3) implies (1): Take the polynomial $p(n) = n$, by assumption we may find a probabilistic polynomial time machine with error probability at most $2^{-n}$. For $n \ge 2$, this is less than $1/3$, and we may hardcode the answers for smaller inputs.

The following are equivalent for any language $L$:

1. $L \in \mathsf{RP}$ (i.e. there is some polynomial-time PTM with one-sided error at most $1/2$).
2. For any $c > 0$, $L$ is decided by a polynomial-time PTM with one-sided error at most $1/2 - n^{-c}$.
3. For any $d > 0$, $L$ is decided by a polynomial-time PTM with one-sided error at most $2^{-n^d}$.

(1) implies (2): If $L \in \mathsf{RP}$, then $L$ is decided by a PTM with one-sided error less than $1/2$, which is stronger than one-sided error less than $1 - 1/\text{poly}( \vert x \vert )$ for $ \vert x \vert $ sufficiently large. If $ \vert x \vert $ is not large enough, we can hard code those inputs.

---

(2) implies (3): Suppose $M$ is the PTM such that for every $x \in \lbrace 0, 1\rbrace^\ast$, $\mathbb P[M(x) = 1 \mid x \in L] \ge \vert x \vert ^{-c}$ and $\mathbb P[M(x) = 0 \mid x \notin L] = 1$.

Consider the PTM $N$ which on input $x$, runs $M(x)$ a number of $k$ times. If any of the runs are accepting, then $N$ accepts. Otherwise, it rejects.

If $x \notin L$, then none of the runs will ever accept. Hence $\mathbb P[N(x) = 0 \mid x \notin L] = 1$.

If $x \in L$, then the probability that none of the runs accept is given by $(1 - \vert x \vert ^{-c})^k$. But since $1 - x \le e^{-x}$, we have

\[\begin{aligned} \mathbb P(N(x) = 0 \mid x \in L) &\le (1 - |x|^{-c})^k \\\\ &\le e^{-|x|^{-c}k} \end{aligned}\]

Hence choosing $k \ge (\ln 2) \cdot \vert x \vert ^{d+c}$ gives

\[\mathbb P(N(x) = 0 \mid x \in L) \le e^{-|x|^{-c} \cdot |x|^c \cdot \ln 2 \cdot |x|^d} = 2^{-|x|^d}\]

as required.

---

(3) implies (1): Take the polynomial $p(n) = n$, by assumption we may find a probabilistic PTM with one sided at most $2^{-n}$. For $n \ge 2$, this is less than $1/2$, and we may hardcode the answers for smaller inputs.

• $\mathsf{P} \subseteq \mathsf{ZPP} \subseteq \mathsf{RP} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE}$
• $\mathsf{RP} \subseteq \mathsf{BPP}$
• $\mathsf{BPP} \subseteq \mathsf{PSPACE}$
• $\mathsf{BPP} \subseteq \mathsf{P} _ {/\mathsf{poly} }$

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.
4. Reduce the error to be $2^{-n-1}$. Count the number of strings $r$ which are bad for some $x$, and see that it’s less than the total number of strings. Hence there’s some string we can hardcode to make it always correct.

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 \lbrace 0, 1\rbrace^\ast$,

\[\mathbb P _ {r \in \lbrace 0 ,1\rbrace^{p( \vert x \vert )} } (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{BPP}$
2. For any non-constant polynomial $p$, $L$ is decided by a probabilistic polynomial-time machine with two-sided error $1/2 - 1/p( \vert x \vert )$.
3. For any non-constant polynomial $p$, $L$ is decided by a probabilistic polynomial-time machine with two-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 \lbrace 0, 1\rbrace^n$, $\mathbb P _ {r \in \lbrace 0, 1\rbrace^m } [M(x, r) \ne L(x)] \le 2^{-n-1}$.

Call a string $r \in \lbrace 0, 1\rbrace^m$ bad if on input $x \in \lbrace 0, 1\rbrace^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$ (since the probability of being incorrect on $x$ is the proportion of bad strings for $x$, which is $\frac{2^m}{2^{n+1} } / 2^m = 2^{-n-1}$). Adding over all $x \in \lbrace 0, 1\rbrace^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 \lbrace 0, 1\rbrace^m$ that is good for every $x \in \lbrace 0, 1\rbrace^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 \lbrace 0, 1\rbrace^n$, as required.

\[\mathsf{ZPP} = \mathsf{RP} \cap \mathsf{coRP}\]

---

Brief justification:

• $\mathsf{ZPP} \subseteq \mathsf{RP} \cap \mathsf{coRP}$: We have $\mathsf{ZPP} \subseteq \mathsf{RP}$ by previous results (just keep a counter and reject if the machine is taking too long). Since $\mathsf{ZPP}$ is closed under complementation, it follows by complementing both sides that $\mathsf{ZPP} \subseteq \mathsf{RP} \cap \mathsf{coRP}$.
• $\mathsf{RP} \cap \mathsf{coRP} \subseteq \mathsf{ZPP}$: If $M$ and $\overline M$ are PTMs with one-sided error $1/4$ deciding $L$ and $\overline L$ respectively, create a new PTM $Z$ which runs $M$, accepts if this accepts, and if not, runs $\overline M$ and rejects if this accepts. If none of these happen, $Z$ should go back to the beginning. Then $Z$ has zero-sided error.

Modify a $\mathsf{ZPP}$ machine so that rather than running for longer than polynomial time, it instead just halts. This forms a $\mathsf{NP}$ machine recognising the same language.

By error reduction results, we may assume that $\mathsf{SAT}$ is decided by a poly-time PTM $M$ with bounded error at most $1/m^2$, where $m$ is the input length.

Define a PTM $N$ deciding $L$ with one-sided error at most half:

• On input $x$:
  • $N$ checks if $x = \varphi$ for some $\varphi$ formula
  • $N$ runs the standard search-to-decision procedure for SAT, answering decision queries by simulating $M$
  • Then it checks that the assignment output by the search-to-decision procedure, if any, satisfies the input $x$.
  • If yes, it accepts, otherwise it rejects.

Clearly $N$ is polynomial time as $M$ is. On any unsatisfiable $x$, $N$ rejects with probability $1$, as it only accepts when it finds a satisfying assignment, and an unsatisfiable $x$ has no satisfying assignments.

On satisfiable $x$, since the error of $M$ is at most $1/m^2$ and the number of calls to the search-to-decision procedure on a formula $x$ of size $m$ is at most $m$, all answers given by the simulation of $M$ are correct with probability at least $1-1/m$ by a union bound, and hence $N$ correctly finds a satisfying assignment to $x$ and accepts with probability at least $1 - 1/m \ge 1/2$ for $m > 1$.

A language $L$ is in $\mathsf{PP}$ if there is a PTM $M$ such that for all $x \in \Sigma^\ast$:

• $M$ runs in time polynomial in $ \vert x \vert $
• If $x \in L$, then the probability of acceptance is $\ge 1/2$
• If $x \notin L$, then the probability of acceptance is $< 1/2$.

We show that $\mathsf{SAT} \in \mathsf{PP}$. Consider the PTM $M$ which on input $\varphi$, computes a random assignment $\pmb x$. Then if $\pmb x$ satisfies $\varphi$, $M$ accepts. Otherwise, it accepts with probability $1/2 - 1/2^{n+1}$ and rejects with probability $1/2 + 1/2^{n+1}$.

Suppose that $\varphi$ is satisfiable. Then $M$ accepts with probability at least

\[\begin{aligned} \frac 1 2 \left( 1 - 2^{-n} \right) \cdot \left(\frac 1 2 - \frac{1}{2^{n+1} }\right) + 1 \cdot 2^{-n} &= \frac 1 2 + 2^{-2n+1} \\ &> \frac 1 2 \end{aligned}\]

If $\varphi$ is not satisfiable, then $M$ accepts with probability $\frac{1}{2} - 2^{n-1} < \frac 1 2$ and hence overall, $\varphi \in \mathsf{SAT}$ iff $M$ accepts $\varphi$ with probability at least $1/2$.

Since $\mathsf{SAT}$ is $\mathsf{NP}$-complete under polynomial time m-reductions, it follows that $\mathsf{NP} \subseteq \mathsf{PP}$.