\documentclass{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{latexsym}
\usepackage{graphicx}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.5in}
\newcommand{\sharpP}{\mathbf{\#P}}
\newcommand{\IP}{\mathbf{IP}}
\newcommand{\PSPACE}{\mathbf{PSPACE}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\vy}{\mathbf{y}}
\newcommand{\header}{
\renewcommand{\thepage}{\arabic{page}}
\noindent
\begin{center}
\framebox{
\vbox{
\hbox to 5.78in {\bf 6.841/18.405J: Advanced Complexity \hfill Monday, March 31st, 2003}
\vspace{2mm}
\hbox to 5.78in { {\Large \hfill Lecture 13\hfill} }
\vspace{2mm}
\hbox to 5.78in { {\it Instructor: Madhu Sudan \hfill Scribe: Chun-Yun Hsiao} }
}
}
\end{center}
\vspace*{3mm}
}
\newtheorem{theorem}{Theorem}
\newtheorem{claim}{Claim}
\begin{document}
\header
Today:
\begin{itemize}
\item $\sharpP \subseteq \IP$
\item $\PSPACE = \IP$
\end{itemize}
In this lecture, we will show that $\PSPACE \subseteq \IP$; together with
$\PSPACE \supseteq \IP$, proved in last lecture, we conclude that $\PSPACE =
\IP$. We proceed by first showing $\sharpP \subseteq \IP$, and then
generalize the proof to showing $\PSPACE \subseteq \IP$.
\section{$\sharpP$ is in $\IP$}
Let's begin by recalling what $\sharpP$ and $\IP$ are:
\begin{itemize}
\item $\sharpP$: class of functions that count the number of accepting paths
of a poly-time NTM. It suffices to consider a $\sharpP$-complete problem.
For practical purposes that will become clear later, we choose the problem
$\#SAT$. That is, given a 3CNF, determine the number of satisfying truth
assignments it has.
\item $\IP$: class of languages $L$, where ``$x \in L$'' has an interactive
proof verifiable by a probabilistic poly-time TM.
\end{itemize}
\paragraph{Self-Reducibility}
Our goal is to show that $\#SAT$ has an interactive proof. More
precisely, given a 3CNF formula $\phi$ and a number $A$, the all-powerful
prover wants to convince the poly-time verifier that $\phi$ has exact $A$
satisfying truth assignments. The idea is to exploit the self-reducibility
of $SAT$. Let $\phi_0$ be the formula $\phi$ with its first variable set to
0, i.e., $\phi_0 \triangleq \phi(x_1=0)$; similarly $\phi_1 \triangleq
\phi(x_1=1)$.
Suppose that we (the verifier) are convinced that the number of truth
assignments of $\phi_0$ and $\phi_1$ are $A_0$ and $A_1$ respectively, then
all we need to do is to check if $A = A_0+A_1$. To make sure that $A_0$ and
$A_1$ are the alleged numbers, we need to check that $A_0 = A_{00} + A_{01}$
and $A_1= A_{10} + A_{11}$,\footnote{$A_{st}$ is defined analogously when
the first two variables are assigned to $s$ and $t$.} and recursively until
all the variables are assigned with a Boolean value so that we can evaluate
the $A$'s ourselves.
\paragraph{Expanding the Tree?}
The problem is that every time we reduce one variable, we double the number
of equations to be verified. To get around with this exponential growth, the
prover, instead of giving $A_0$ and $A_1$, will provide us a function $Q_1$
such that $Q_1(0)$ and $Q_1(1)$ (are supposed to) represent the number of
satisfying truth assignments of $\phi_0$ and $\phi_1$, respectively. Then
the prover will provide another function $Q_2$ to convince us that $Q_1$ is
the ``right'' function, and $Q_3$ for the validity of $Q_2$ and so on. The
protocol proceeds until finally we can verify the validity of $Q_n$ by
ourselves. More precisely, we know that\footnote{Here the output of $\phi$
is viewed as an integer.}
\begin{eqnarray*}
A & = & \sum_{(x_1,\ldots,x_n) \in \{0,1\}^n} \phi(x_1,x_2,\ldots,x_n)\\
& = & \sum_{x_1\in \{0,1\}} \sum_{x_2\in \{0,1\}} \cdots
\sum_{x_n \in \{0,1\}} \phi(x_1,x_2,\ldots, x_n).\\
\end{eqnarray*}
Let's define functions $Q$'s without worrying how to represent them
(efficiently) first. Naturally,
$$Q_1(x_1) \triangleq \sum_{x_2\in\{0,1\}} \sum_{x_3\in\{0,1\}} \cdots
\sum_{x_n\in\{0,1\}} \phi(x_1,x_2,\ldots,x_n),$$
since this way $Q_1(0)+Q_1(1)$ is equal to $A$. We can generalize the
definition to $Q_i$, for each $i$,
$$Q_i(x_1,x_2,\ldots,x_i) \triangleq \sum_{x_{i+1}\in \{0,1\}} \sum_{x_{i+2}\in
\{0,1\}} \cdots \sum_{x_n\in\{0,1\}} \phi(x_1,x_2,\ldots,x_n).$$
An ideal way of representing the $Q$'s is by polynomials. For the polynomial
representation to be meaningful, we require that they agree with our
definition on binary inputs. To this end, we need an arithmetic way of
looking at $\#SAT$.
\paragraph{Arithmetization}
Consider the following transformation from Boolean formulae to arithmetic
polynomials.
\begin{center}
\frame{\begin{tabular}{ccc}
Boolean & & Arithmetic\\
\hline
$\bar{x_1}$ & $\rightarrow$ & $1-x_1$\\
$C_j=(x_1 \vee \bar{x_2} \vee x_3)$ & $\rightarrow$ &
$P_j=1-(1-x_1)x_2(1-x_3)$\\
$\phi(x_1,x_2,\ldots,x_n)=C_1 \wedge C_2 \wedge \cdots \wedge C_m$ &
$\rightarrow$ & $P(x_1,x_2,\ldots,x_n)=\prod_{j=1}^{m}
P_j(x_1,x_2,\ldots, x_n)$\\
\end{tabular}}
\end{center}
It is easy to see that the polynomial $P$ agrees with the formula $\phi$
on binary inputs $\{0,1\}^n$. And we can ``redefine'' the function $Q_i$ in
terms of $P$, namely for each $i$,
$$Q_i(x_1,x_2,\ldots,x_i) \triangleq \sum_{x_{i+1}\in \{0,1\}} \sum_{x_{i+2}\in
\{0,1\}} \cdots \sum_{x_n\in\{0,1\}} P(x_1,x_2,\ldots,x_n).$$
Note that now each $Q_i$ is indeed a polynomial. Furthermore, they are all
of degree at most $3m$; ``efficient'' representation exists. The
question is how do we verify these $Q_i$ are derived honestly from
$P(x_1,x_2,\ldots,x_n)$? Recall, from the definition, that the polynomial
$Q_i(x_1,x_2,\ldots,x_i)$ should be identical to
$Q_{i+1}(x_1,x_2,\ldots,x_i,0) + Q_{i+1}(x_1,x_2,\ldots,x_i,1)$. If we can
verify their equality on a random input, they are identical with good
probability. For
our purposes, all arithemic operations will be done modulo some large prime
$p$. Here is the protocol.
\begin{center}
\frame{\begin{tabular}{ccc}
$\swarrow$ & $(\phi,A)$ & $\searrow$\\
{\bf Verifier} & & {\bf Prover}\\
REJECT if $p$ not prime &$\stackrel{p}{\longleftarrow}$ &
pick prime $p \in\{0,1\}^{n+1}$\\
\hline
REJECT if $h_1(0)+h_1(1) \ne A$ & $\stackrel{h_1(\cdot)}{\longleftarrow}$ &
send coefficients of $Q_1(\cdot)$\\
wonder ``$h_1(\cdot) \stackrel{?}{=}Q_1(\cdot)$'' &&\\
challenge $\alpha_1 \in_{\rm R} \Z_p$ &
$\stackrel{\alpha_1}{\longrightarrow}$ &
show ``$A_1 \triangleq h_1(\alpha_1) = Q_1(\alpha_1)$''\\
\hline
REJECT if $h_2(0)+h_2(1) \ne A_1$ & $\stackrel{h_2(\cdot)}{
\longleftarrow}$ & send coefficients of $Q_2(\alpha_1,\cdot)$\\
wonder ``$h_2(\cdot) \stackrel{?}{=}Q_2(\alpha_1,\cdot)$'' &&\\
challenge $\alpha_2 \in_{\rm R} \Z_p$ &
$\stackrel{\alpha_2}{\longrightarrow}$ & show ``$A_2 \triangleq h_2(\alpha_2)
=Q_2(\alpha_1,\alpha_2)$''\\
\hline
REJECT if $h_i(0)+h_i(1) \ne A_{i-1}$ & $\stackrel{h_i(\cdot)}{
\longleftarrow}$ & send $Q_i(\alpha_1,\ldots,\alpha_{i-1},\cdot)$\\
wonder ``$h_i(\cdot) \stackrel{?}{=}
Q_i(\alpha_1,\ldots,\alpha_{i-1},\cdot)$''&&\\
challenge $\alpha_i \in_{\rm R} \Z_p$ &
$\stackrel{\alpha_i}{\longrightarrow}$ & show ``$A_i \triangleq
h_i(\alpha_i)=Q_i(\alpha_1,\ldots,\alpha_i)$''\\
\hline
REJECT if $h_n(0)+h_n(1) \ne A_{n-1}$ & $\stackrel{h_n(\cdot)}{
\longleftarrow}$ & send $Q_n(\alpha_1,\ldots,\alpha_{n-1},\cdot)$\\
$\alpha_n \in_{\rm R} \Z_p$ &&\\
REJECT if $h_n(\alpha_n) \ne Q_n(\alpha_1,\alpha_2,\ldots,\alpha_n)$ \\
ACCEPT
\end{tabular}}
\end{center}
Note that $Q_n(\alpha_1,\alpha_2,\ldots,\alpha_n) =
P(\alpha_1,\alpha_2,\ldots,\alpha_n)$ can be computed by ourselves.
\paragraph{Completeness}
If indeed $\phi$ has $A$ satisfying truth assignments, the honest prover
just follows the protocol and sends the correct $h_i$, which is
$Q_i(\alpha_1,\ldots,\alpha_{i-1}, \cdot)$. The verifier will accept with
probability one.
\paragraph{Soundness}
Suppose that $\phi$ has $A' \ne A$ satisfying truth assignments.
Inductively, if $Q_{i-1}(\alpha_1,\ldots,\alpha_{i-1}) \ne A_{i-1}$, then
$$h_i(0) + h_i(1) =
A_{i-1} \ne Q_{i-1}(\alpha_1,\ldots,\alpha_{i-1}) =
Q_i(\alpha_1,\ldots,\alpha_{i-1},0) + Q_i(\alpha_1,\ldots,
\alpha_{i-1},1).$$
The first equality is assured by verifier's check, otherwise it would reject
immediately. The last equality is by the definition of $Q$ and the
inequality is the inductive assumption. So we know that $h_i(\cdot) \ne
Q_i(\alpha_1,\ldots,\alpha_{i-1},\cdot)$; with probability $1-\frac{3m}{p}$,
$\alpha_i$ is not a rooot of $h_i(\cdot)-
Q_i(\alpha_1,\ldots,\alpha_i-1,\cdot)$. Thus $h_i(\alpha_i) \ne
Q_i(\alpha_1,\ldots,\alpha_i)$.
By union bound, the soundness is at least $1-\frac{3mn}{p}$.
\paragraph{Remark} Notice that the verifier only tosses \emph{public} coins.
This is another ``indication'' that $\IP$ is no more powerful than
Athur-Merlin game.
\section{$\PSPACE = \IP$}
This result is somewhat surprising, in the following sense.
\begin{itemize}
\item We don't know (expect) that $\IP$ is closed under complement.
\item There exists an oracle $O$ such that $\IP^O \nsupseteq
(\mathbf{\Sigma}^P_i)^O$.
\end{itemize}
\paragraph{Abstract of the Proof}
Note that in last section the proof didn't use any specific feature of
$\sharpP$. The key idea is only the downward self-reducibility. Let's
look at the proof abstractly and see if it could lead us to showing
$\PSPACE \subseteq \IP$.\footnote{In fact every self-reducible
language is in $\PSPACE$ and as we shall see in next lecture that every
language in $\PSPACE$ is self-reducible.}
\begin{enumerate}
\item $Q_0, Q_1, \ldots, Q_n$ is a sequence of low-degree polynomials.
\item $Q_0() = A$.
\item $Q_n$ is a polynomial we can evaluate on any input by ourselves.
\item $Q_i$ can be computed in poly-time, give non-adaptive oracle queries
to $Q_{i+1}$.
\begin{itemize}
\item For example, $Q_i(\alpha_1,\ldots,\alpha_i)=
Q_{i+1}(\alpha_1,\ldots,\alpha_i,0)+Q_{i+1}(\alpha_1,\ldots,\alpha_i,1)$.
\item In general, $Q_i(\vy)$ can be computed from $Q_{i+1}(\vy_1),
Q_{i+1}(\vy_2), \ldots,Q_{i+1}(\vy_\ell)$, where $\vy_j$ can be computed
from $\vy$.
\end{itemize}
\end{enumerate}
Condition 4 is the most important one that saves us from exponential
fan-out. Indeed, if we are only concerned about $Q_{i+1}$ on $\vy_1,\ldots,
\vy_{\ell}$, we may focus on $Q_{i+1}|_C$, where $C$ is a curve passing
through $\vy_1,\ldots,\vy_\ell \in \Z^n_p$.
Let us formalize the above discussion. A curve $C$ is a function
(polynomial) from $\Z_p$ to $\Z^n_p$. $$C=(C_1,C_2,\ldots,C_n),
\textrm{ where each } C_i: \Z_p \rightarrow \Z_p \textrm{ is a
polynomial.}$$
The degree of $C$ is the maximum degree of $C_i$, i.e., $\max_i\{{{\rm deg}(
C_i)}\}$. Here are some useful factoids.
\begin{itemize}
\item Given $\vy_1,\vy_2,\ldots,\vy_\ell \in \Z_p^n$, there exists degree
$\ell -1$ curve $C$ such that $C(i) = \vy_i$, $\forall i =1,2,\ldots,\ell$.
\item Let $Q: \Z_p^n \rightarrow \Z_p$ be degree $d$ polynomial, and $C:\Z_p
\rightarrow \Z_p^n$ be degree $\ell$ polynomial. Then $Q|_C:\Z_p \rightarrow
\Z_p$ is a polynomial of degree at most $d\ell$. We can write $Q|_C(t) =
Q(C(t))$.
\end{itemize}
In general at the $i^{th}$ round, we want to verify the validity of
$h_i(\cdot)$, which is received in the previous round. We pick a random
$\vy \in \Z_p^n$, compute the curve $C$ and send it to the prover. The
prover respond with $h_{i+1}$ which is supposed to be $Q_{i+1}|_C$. Since
$C$ passes through $\vy_1,\vy_2,\ldots, \vy_\ell$, we are able to compute
$h_i(\vy)$ and notice any inconsistency so far, with good probability.
It turns that the curve $C$ doesn't need to be complicated at all;
straight lines will suffice for our purposes to show $\PSPACE \subseteq
\IP$. We will elaborate more in the next lecture.
%\begin{center}
%\includegraphics[scale=.65]{.eps}
%\end{center}
\begin{thebibliography}{10}
\bibitem[LFKN90]{LFKN90}
Carsten Lund, Lance Fortnow, Howard J. Karloff, and Noam Nisan. Algebraic
Methods for Interactive Proof Systems. \emph{FOCS} 1990: 2-10.
\bibitem[Sha90]{Sha90}
Adi Shamir. IP=PSPACE. \emph{FOCS} 1990: 11-15.
\bibitem[Sud02]{Sud02}
Madhu Sudan. 6.841/18.405J: Advanced Complexity Theory, Lecture 14, 2002.
{\tt http://theory.lcs.mit.edu/\~{}madhu/ST02/scribe/lect14.ps}.
\end{thebibliography}
\end{document}