\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{epsfig}

\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}
\newcommand{\handout}[5]{
   \renewcommand{\thepage}{#1-\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in { {\bf 18.405J/6.841J Advanced
  Complexity Theory} \hfill #2 }
       \vspace{4mm}
       \hbox to 5.78in { {\Large \hfill #5  \hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it #3 \hfill #4} }
      }
   }
   \end{center}
   \vspace*{4mm}
}

\newcommand{\lecture}[4]{\handout{#1}{#2}{Lecturer:
#3}{Scribe: #4}{Lecture #1}}

\makeatletter
\def\fnum@figure{{\bf Figure \thefigure}}
\def\fnum@table{{\bf Table \thetable}}
\long\def\@mycaption#1[#2]#3{\addcontentsline{\csname
  ext@#1\endcsname}{#1}{\protect\numberline{\csname 
  the#1\endcsname}{\ignorespaces #2}}\par
  \begingroup
    \@parboxrestore
    \small
    \@makecaption{\csname fnum@#1\endcsname}{\ignorespaces #3}\par
  \endgroup}
\def\mycaption{\refstepcounter\@captype \@dblarg{\@mycaption\@captype}}
\makeatother

\newcommand{\bigO}{\text{O}}
\newcommand{\hp}{\text{\#}P}
\newcommand{\op}{{\oplus}P}
\newtheorem{theorem}{Theorem}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\newtheorem{claim}[theorem]{Claim}
\newcommand{\qed}{\rule{7pt}{7pt}}
\newenvironment{proof}{\noindent{\bf Proof}\hspace*{1em}}{\qed\bigskip}
\begin{document}
\lecture{21}{April 30, 1998}{Daniel A. Spielman}{Yoav Yerushalmi}

In this lecture, we will prove the following two things:
\begin{itemize}
\item $\hp \subseteq IP$
\item $IP(poly) = PSPACE$
\end{itemize}

The former result is only used as a basis for seeing how to prove the
latter. However, the fact that an interactive protocol with a
polynomial number of rounds is equivalent to a machine running in
polynomial space was a surprising result.

In this lecture, we will only actually prove this for public coins
(that is we will show that $AM(poly) = PSPACE$).

\section{$\hp \subseteq IP$}

This fact was proven using arithmetization. The idea behind
arithmetization is to convert the problem (claim/language) into a
mathematical problem, and then use well established mathematical
formulas to reduce or modify the problem to one that can be solved by
our machine.

\begin{example}[Arithmetization of 3CNF]
Given a 3CNF, we let the variables in the 3CNF formula be variables of
a polynomial, where if a variable's value in the polynomial is 0 it
means the variable is {\bf false} in the 3CNF, and vice-versa.
\begin {eqnarray*}
not(x_i) & = & 1-x_i \\
x_1 \wedge x_2 & = & x_1 \cdot x_2 \\
x_1 \vee x_2 & = & 1 - (1-x_1)(1-x_2) \\
(x_1 \vee x_2 \vee \overline{x_3}) & = & 1 - (1-x_1)(1-x_2)(x_3)\\
\end{eqnarray*}
The second to last formula was derived by DeMorgan's law.  Each of
thee clauses in the 3CNF lead to a degree 3 polynomial. All these
polynomials are multiplied (AND) together. The polynomial can equal 1
if and only if the entire equation had a satisfying assignment.
\end{example}

The reason we use this polynomial, however, is that it can take inputs
in a domain OTHER than $\{0,1\}$. So, now say we want to convince a
verifier that we know the number of satisfying assignments toa
3CNF. This is analogous to making the claim that we know the value of
the following function:
\[ F() = \sum_{x_1 \in \{0,1\}}  \quad \sum_{x_2 \in \{0,1\}} \cdots
\sum_{x_n \in \{0,1\}} p(x_1, x_2, \cdots, x_n) \]
The problem is that the verifier doesn't have the required amount of
time complexity to compute the above function. Our trick will be to
use the prover's extra power to convince the verifier that the value
it claims for the above equation is true by convincing him that an
equation that is directly related to the above, but that the verifier
CAN compute, is correct.

If $P$ can convince $V$ that the value for $F()$ it has provided is
the correct number of satisfying assignments to the 3CNF formula, then
we know that $\hp \subseteq IP$. In order to do this, we need a way to
reduce the equation above. We use a construct named $\epsilon$-links
to do that.

\begin{definition}[$\epsilon$-link]
An $\epsilon$-link is an IP(poly) protocol that takes a proposition
$A$ to another proposition $B$. That is:
\begin{itemize}
\item if $A$ is true, then $\exists P$ prover such that the
proposition $B$ is also true.
\item if $A$ is false, then $\forall P$ provers, the probability that
$B$ is true and the verifier $V$ fails to detect a deception is $\leq
\epsilon$.
\end{itemize}
\end{definition}

Ideally, we only care for $\epsilon$-links that simplify $A$. If we
have an $\epsilon$-link for $A$, we can use $B$ to convince $V$ with
probability  $\geq 1-\epsilon$.

Our proof of $\hp \subseteq IP$ will involve a chain of links that
take the difficult 3CNF polynomial to a simple one that $V$ can
perform to convince itself that $P$ has computed $\hp$. We will have
an error bound which is the sum of all the errors we encounter (one
per link), so we will need to set our $\epsilon$ to be small.

Our first $\epsilon$-link will take our original claim:
\[ A: \quad \left[ \sum_{x_1 \in \{0,1\}}  \quad \sum_{x_2 \in \{0,1\}} \cdots
\sum_{x_n \in \{0,1\}} p(x_1, x_2, \cdots, x_n) \right] = C \]
to a new claim $B$ using the following protocol:
\begin{enumerate}
\item $P \longrightarrow V$ a polynomial of one variable $q_1()$ which
will be directly related to the $x_1$ value thus:
\[ q_1(x_1) = \sum_{x_2 \in \{0,1\}}  \quad \sum_{x_3 \in \{0,1\}} \cdots
\sum_{x_n \in \{0,1\}} p(x_1, x_2, \cdots, x_n) \]
\item $V$ checks that $q_1(0) + q_1(1) = C$. If this is not the case,
we know that the polynomial was not computed correctly or the value we
were given for $C$ was wrong. Therefore, we reject.
\item $V$ then chooses an $\alpha$ at random from a field which we
shall name ${\mathbb F}$ and decide its size to adjust for $\epsilon$
(computation for its size will be done later). $V$ tells $\alpha$ to
$P$, and they now have a simpler equation to work with:
\[ B: \quad \left[ \sum_{x_2 \in \{0,1\}}  \quad \sum_{x_3 \in \{0,1\}} \cdots
\sum_{x_n \in \{0,1\}} p(\alpha, x_2, \cdots, x_n) \right] = q_1(\alpha) \]
\end{enumerate}

\begin{claim}
The above protocol is an $\epsilon$-link from $A$ to $B$.
\end{claim}
\begin{proof}
\begin{enumerate}
\item if $A$ is true, and $P$ follows the protocol, $B$ is clearly
true.
\item if $A$ is not true, then $B$ is very likely to be false: Let $N
= |{\mathbb F}|$ (choose $N$ prime).  If $A$ is false, then
\[ \Pr_\alpha \left[ q_1(\alpha) = \sum_{x_2 \in \{0,1\}}  \quad \sum_{x_3 \in \{0,1\}} \cdots
\sum_{x_n \in \{0,1\}} p(\alpha, x_2, \cdots, x_n) \right] \leq \frac{deg(p)}{N} \]
(We know that $deg(p) \geq(q_1)$). We set $\epsilon =
\frac{deg(p)}{N}$, and voila.
\end{enumerate}
\end{proof}

We now have a polynomial that has one less variable ($x_1$ has been
replaced by a more complex polynomial that absorbs $\alpha$). We are
one step closer to making it possible for $V$ to compute $p()$. We now
have to repeat this idea to reduce the polynomial by eliminating one
variable at a time. This leaves us with a remaining proposition:
\[ p(\alpha_1, \alpha_2, \alpha_3, \hdots, \alpha_n) = C_n \]
Which the verifier can easily check, although we have now introduced
$n$ error terms.

If the verifier accepts, the probability that the initial claim was
false is at most $n \cdot \epsilon = n \cdot \frac{deg(p)}{N}$. So, we
simply set $N \gg n \cdot deg(p)$ to ensure a low probability. if $N$
is exponential, we get $< 1/poly()$ error.

We have now shown that we can simulate $\hp$ using $IP$ where $P$
knows the solution, so we've shown that $\hp \subseteq IP(poly)$.

\section {$IP(poly) = PSPACE$}
Now we get onto the impressive result, using stuff we built on in the
previous section. We demonstrate this fact using the standard
technique of showing that $IP \subseteq PSPACE$ and that $IP
\supseteq PSPACE$.

\subsection {$IP(poly) \subseteq PSPACE$}
This is certainly the easier one of the pair. In fact, it's
intuitive. We can simulate the $IP$ protocol using the $PSPACE$
machine.

\subsection {$IP(poly) \supseteq PSPACE$}
We earlier showed that, given $p(x_1, x_2, \hdots, x_n)$ of polynomial
degree, there is an $\epsilon$-link from the assertion that
\[ \sum_{x_1 \in \{0,1\}}  \quad \sum_{x_2 \in \{0,1\}} \cdots
\sum_{x_n \in \{0,1\}} p(x_1, x_2, \cdots, x_n) = C \] to
\[ p(\alpha_1, \alpha_2, \alpha_3, \hdots, \alpha_n) = C_n \quad
\text{ with } 1/poly() \text{ error}\]

this time we're going to have polynomials $V$ can't verify, but $P$
will convince $V$ of value of polynomial.  Recall the proof from an
earlier lecture that Alternating P-time equals PSPACE. We will follow
a similar line:
\begin{itemize}
\item begin with a PSPACE machine $M$ which works on input $w$.
\item associate with it a graph. The nodes of the graph correspond to
possible (head,tape,state) configurations of the machine, and the
edges correspond to legal transitions.
\item accept if and only if there is a path from the start node to an
accepting node (in this case, there is only one such path since the
machines are both deterministic).
\end{itemize}
We then invented a function named $FromTo(x,y,m)$, which was true if you
could go from node $x$ to node $y$ in $\leq m$ steps. And we made
assertions such as
\[ FromTo(a,b,i) = \exists_z \left( FromTo(a,z,\lfloor i/2 \rfloor)
\wedge FromTo(z,b,\lceil i/2 \rceil) \right) \]

Our base case: $FromTo(x,y,1)$ can be evaluated in polynomial time.
Also, $FromTo(x,y,1)$ can be evaluated by a 3CNF, which can be
evaluated by a polynomial of degree poly(n). It variables are the bits
of $x$ and $y$.

The idea is to start from the original claim $FromTo(x,y,j)$ (using
$m$ bit strings to represent $x,y,j$, and reduce it to a
multiplication (and) of lots of $FromTo$'s os size one using the
following principle:
\[ FromTo(x,y,j) = \sum_{z_1 z_2 z_3 \cdots z_m} FromTo(x,z, j/2)
\cdot FromTo(z,y,j/2) \]

This idea will be explored further and proved in the next lecture.
\end{document}