2026-10-26 TOC Scribe
$\newcommand{\BPL}{\mathbf{BPL}}$ $\newcommand{\P}{\mathbf{P}}$ $\newcommand{\RL}{\mathbf{RL}}$ $\newcommand{\L}{\mathbf{L}}$ $\newcommand{\NL}{\mathbf{NL}}$ $\newcommand{\RP}{\mathbf{RP}}$ $\newcommand{\PSPACE}{\mathbf{PSPACE}}$ $\newcommand{\IP}{\mathbf{IP}}$ $\newcommand{\poly}{\mathsf{poly}}$ $\newcommand{\SAT}{\mathsf{SAT}}$ $\newcommand{\IP}{\mathbf{IP}}$ $\newcommand{\qq}{\quad\quad}$
Quiz Discussion
$\RL\subseteq\RP$ can be proved via $\RL \subseteq \BPL \subseteq \P \subseteq \RP$
We know that $\BPL$ and $\RL$ take up only $c\cdot\log n$ space and have appropriate error bounds. Hence the size of their configuration is only $c\cdot\log n$. The number of configurations is then $2^{c \log n} = \poly(n)$
We’ve seen a similar proof for $\L \subseteq \P$. Since the configuration graph is polynomial a poly TM can easily traverse it in polynomial time.
But that won’t work here. A PTM may not loop forever.
Unlike a TM, PTM may run for a LONG time. Our rationale was that as TM has to halt it cannot have any loops. But for PTM, as it is random, can have loops and still halt. The figure above illustrates this.
Hence we cannot use the same logic here to prove and require something different.
We are still proving $\PSPACE \subseteq \IP$
Remember sharp SAT
$$ \#\SAT_D = \{<\phi, k>:\phi\text{ has exactly }k\text{ solutions}\} $$The $D$ means that this is a decision problem. We can arithmetize this as
$$ \phi(x_1, \ldots, x_n) = p(x_1, \ldots, x_n) $$We also know that
$$ \sum p(x_1 \ldots x_n) = k\mod p $$$p$ is a sufficiently large prime from $p \in (2^n, 2^{2n}]$
We describe the following $\IP$ protocol
| Prover | Verifier |
|---|---|
| Send $s(x_1) = \sum_{b_2\ldots b_n} g(x_1, b_2 \ldots b_n)$ | |
| Check $s(0) + s(1) = k$ | |
| If so, $a \gets \text{GF}(p)$ | |
| Send $s(a), a$ | |
| Recursively compute $\sum_b g(a, b_2\ldots b_n) = s(a)$ |
Claim
$$ \text{False Statement} = \forall P, \Pr[\text{Out}_V(P, V) = 1] \le (1 - \frac{d}{p})^n\\ \text{True Statement} = \exists P \text{ s.t. } \Pr[\text{Out}_V(P, V) = 1] = 1\\ $$Let us see when this false statement can occur
$$ s(x_1) \ne \sum_{b_2\ldots b_n} g(x_1, b_2 \ldots b_n) $$