\documentclass{article}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{amsthm}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.5in}
\setlength{\textheight}{8.5in}

\newcommand{\header}[5]{
   \renewcommand{\thepage}{\arabic{page}}
   \noindent
   \begin{center}
   \framebox{
      \vbox{
    \hbox to 5.78in {\bf {#1} \hfill {#2}}
       \vspace{2mm}
       \hbox to 5.78in { {\Large \hfill Lecture {#3}\hfill} }
       \vspace{2mm}
       \hbox to 5.78in { {\it Instructor: {#4} \hfill Scribe: {#5}} }
      }
   }
   \end{center}
   \vspace*{3mm}
}

\newcommand{\ip}{\hbox{\bf IP}}
\newcommand{\mip}{\hbox{\bf MIP}}
\newcommand{\oip}{\hbox{\bf OIP}}
\newcommand{\pspace}{\hbox{\bf PSPACE}}
\newcommand{\nexp}{\hbox{\bf NEXP}}
\newcommand{\corp}{\hbox{\bf co-RP}}
\newcommand{\np}{\hbox{\bf NP}}
\newcommand{\pcp}{\hbox{\bf PCP}}
\newcommand{\Z}{\hbox{\bf Z}}
\newcommand{\poly}{\hbox{poly}}


\begin{document}
\header{6.841/18.405J: Advanced Complexity}{Wednesday, April 2, 2003}
{Lecture 14}{Madhu Sudan}{Dion Harmon}

In this lecture we cover
\begin{itemize}
\item $\ip = \pspace$
\begin{itemize}
\item Interactive proof for straightline programs.
\item Straightline program for $\pspace$.
\end{itemize}
\item Other definitions of proofs (and nice applications).
\begin{itemize}
\item Multi-prover interactive proofs ($\mip$) and $\mip=\nexp$.
\item Oracle Interactive Proofs.
\item Probabilistically Checkable Proofs (PCP's).
\end{itemize}
\end{itemize}

\section{$\ip = \pspace$}
We have left to show that $\pspace\subseteq \ip$.  We do this by using
straightline programs of polynomials.  We first show there is an
interactive proof to evaluate any straightline program of a certain
type and then show that any $L\in\pspace$ has a nice straightline
program of the same type.

\subsection{Straightline Programs of Polynomials}

A straightline program of polynomials is characterized by four
parameters:  $n$, $L$, $w$, and $d$.
\begin{description}
\advance\leftskip by 0.5in
\item[$n$] The number of variables.
\item[$L$] The number of polynomials (minus 1).
\item[$w$] The width of the program.
\item[$d$] The degree of the program.
\end{description}
The program consists of polynomials $P_0,\ldots,P_L$ each of degree at
most $d$ in at most $n$ variables.  Polynomial $P_i$ is easy to evaluate in
polynomial time with at most $w$ calls to $P_{i-1}$.   We will deal with $w=2$
today.  We are interested in verifying claims of the form $P_L(z)=a$.  

\subsection{Lines in $\Z_p^n$}

Algebraically a line in $\Z_p^n$ is a set
\begin{equation}
\label{eqn:line-zp}
\ell_{xy} = \left\{\left.\ell_{xy}(t)\right|t\in\Z_p\right\}
=
\left\{\left.\left[
  \begin{array}{c}
(1-t)x_1+y_1\\
(1-t)x_2+y_2\\
\vdots\\
(1-t)x_n+y_n\\
\end{array}\right]\right|t\in\Z_p\right\}
\end{equation}
where $x$ and $y$ are elements of $\Z_p^n$.  The definition of a
function $p$ from $\Z_p^n$ to $\Z_p^n$ restricted to a line is now
straightforward:
$$
\begin{array}{rcl}
p&:&\Z_p^n\mapsto\Z_p\\
p|_\ell&:&\Z_p\mapsto\Z_p \quad\hbox{such that}\quad
p|_\ell(t) = p(\ell(t)).\\
\end{array}
$$ 
where $\ell(t)$ is defined as in equation~(\ref{eqn:line-zp}).  Note
that if a function $P$ has degree $d$ in $\Z_p^n$ then the restriction
of $P$ to a line $\ell$ has the same degree (in $x$, $y$, and $t$
variables).  

\subsection{Interactive Proof for some width 2 straightline programs.}
\label{sec:w2-straight}

We consider straightline programs of the form
$$
P_i(x) = P_{i-1}(f_i(x))\ \ \sigma_i \ \  P_{i-1}(g_i(x))
$$
where $\sigma_i\in\{+,\cdot\}$ and $f_i$ and $g_i$ are polytime
computable. 

We want to see if $P_L(z_L)=a_L$.  For the first step we do the following:
\begin{description}
\item[Round 1:]Both $V$ and $P$ compute $x_L=f_L(z_L)$ and
  $y_L=g_L(z_L)$.  
\item[Round 2:] $P$ sends $V$ a polynomial $h_L(t)$ which is supposed
  to be $P_{L-1}(\ell_{x_L,y_L}(t))$.  
\item[Round 3:] $V$ checks to make sure that $a_L=h_L(0)\ \sigma_L\
  h_L(1)$.  If not, $V$ rejects.  Otherwise $V$ picks $t_L$ randomly
  in $\Z_p$.  Let $z_{L-1}=\ell_{x_L,y_L}(t_L)$ and
  $a_{L-1}=h_L(t_L)$.  
\end{description}
$P$ and $V$ verify recursively that $P_{L-1}(z_{L-1})=a_{L-1}$. We end
at the question, ``Does $P_0(z_0)=a_0$?'' and the verifier can compute
this in poly time.

This is sound and complete:
\begin{description}
\item[Completeness] The prover is honest and computes $h_i=P_i|\ell_i$
  at each step and the verifier will not reject: we accept with
  probability 1.
\item[Soundness] If $P_i(z_i)\ne a_i$ and the verifier does not reject
  during step $L-i+1$ then with probability $1-d/p$
  $P_{i-1}(z_{i-1})\ne a_{i-1}$ and the inequality is preserved.  The
  inequality is preserved with probability $(1-d/p)^L\ge 1-dL/p$
  through all steps.  The verifier checks for itself if
  $P_0(z_0)=a_0$.  If $P_L(z_L)\ne a_L$ it will discover $P_0(z_0)\ne
  a_0$ with probability $\ge 1-dL/p$.  Picking $p$ larger than $2dL$
  gives us the necessary bound.
\end{description}

\section{Straightline polynomials produce all of $\pspace$}

\subsection{Description of polynomials used}

We use only the types of polynomials described at the beginning of
section~\ref{sec:w2-straight}.  Our polynomials are $P_i(x,y)$ and
$Q_{i,j}(x,y,z_1,\ldots,z_j)$, where $x$ and $y$ are length $n$
vectors in $\Z_p^n$ and $z_i\in\Z_p$.  If the input vectors $x$ and
$y$ are length $n$ bit vectors (0's and 1's) then we interpret them as
configurations of some $\pspace$ machine $M$.  The vectors $x$ and $y$
have no special meaning if they are not bit vectors.  For state
vectors $x$ and $y$ let
$$
P_i(x,y)=\left\{
\begin{array}{rl}
1&\ \hbox{if $M$ goes from $x$ to $y$ in exactly $2^i$ steps}\\
0&\ \hbox{otherwise}\\
\end{array}\right.
$$

To get $P_{i}$ from $P_{i-1}$, consider some state $z$ that is halfway
between $x$ and $y$ in the execution of $M$.  We have
$P_{i-1}(x,z)=P_{i-1}(z,y)=1$.  Execution of $M$ is deterministic so
there is only one such $z$ (in $\{0,1\}^n$).  Thus
$$
P_{i}(x,y)=\sum_{\hbox to 0pt{\hss$\scriptstyle z\in\{0,1\}^n$\hss}}
P_{i-1}(x,z)\cdot P_{i-1}(z,y).
$$

It takes exponential time to sum over all such $z$ so we use the
$Q_{i,j}$ polynomials to evaluate the sum efficiently:
$$
\begin{array}{rcl}
Q_{i,n}(x,y,\underbrace{z_1,\ldots,z_n}_{z\in\Z_p^n})&=&
P_{i-1}(x,z)\cdot P_{i-1}(z,y)\\
Q_{i,j}(x,y,z_{1},\ldots,z_j)&=&Q_{i,j+1}(x,y,z_1,\ldots,z_j,0) +
 Q_{i,j+1}(x,y,z_1,\ldots,z_j,1)\\
\end{array}
$$
Thus
$$
Q_{i,0}=\sum_{z\in\{0,1\}^n}P_{i-1}(x,z)\cdot P_{i-1}(z,y)=P_{i}(x,y).
$$
Our polynomials (in order) for the straightline program are
$$
P_{0}, Q_{1,n}, \ldots, Q_{1,0}, P_{1}, Q_{2,n},\ldots,Q_{2,0},P_{2},
\ldots,P_{L}.
$$

Our program has width $2$ and length $n^2$.  The degree of this
straightline program is discussed below.

\subsection{Degree of $P_0$}

We can give $P_0$ explicitly in terms of single step of the machine:
$$
P_0(x,y) =
\prod_{j=1}^{n}\left(
\vcenter{\vskip0.2cm\hbox{\hskip0.04cm\setlength{\unitlength}{0.7cm}
\begin{picture}(3,2)
\put(0,2){\line(1,0){3}}
\put(0,1){\line(1,0){1}}
\put(2,1){\line(1,0){1}}
\put(1,0){\line(1,0){1}}
\put(0,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}
\put(0,1){\makebox(1,1){\hfil$x_{i-1}$}}
\put(1,1){\makebox(1,1){$x_{i}$}}
\put(2,1){\makebox(1,1){$x_{i+1}$\hfil}}
\put(1,0){\makebox(1,1){$y_i$}}
\end{picture}\hskip0.1cm}\vskip0.1cm}
\right)
$$
where $n$ is the total amount of space used in the computation.  The
polynomial represented by
$$
\vcenter{\vskip0.2cm\hbox{\hskip0.04cm\setlength{\unitlength}{0.7cm}
\begin{picture}(3,2)
\put(0,2){\line(1,0){3}}
\put(0,1){\line(1,0){1}}
\put(2,1){\line(1,0){1}}
\put(1,0){\line(1,0){1}}
\put(0,1){\line(0,1){1}}
\put(3,1){\line(0,1){1}}
\put(1,0){\line(0,1){1}}
\put(2,0){\line(0,1){1}}
\put(0,1){\makebox(1,1){\hfil$x_{i-1}$}}
\put(1,1){\makebox(1,1){$x_{i}$}}
\put(2,1){\makebox(1,1){$x_{i+1}$\hfil}}
\put(1,0){\makebox(1,1){$y_i$}}
\end{picture}\hskip0.1cm}\vskip0.1cm}
$$ is one if $y_i$ is the appropriate bit given the $x$ bits and $0$
otherwise.  It is of some constant degree at most $D$ in $x_i$'s and
$y_i$'s.  The degree of $P_0(x,y)$ in any one $x$ variable is at most
$3D$ and $D$ in any $y$ variable.  Thus $P_0(x,y)$ is of degree at most $3nD$
which is polynomial in the input size.

\subsection{Degree of other polynomials}

Assume $P_{i-1}$ is of degree at most $d$ in any one variable (the
total degree may be $nd$).  The expression for $Q_{i,n}$ indicates it
can be degree at most $d$ in any $x$ or $y$ variables and $2d$ in any
$z$.  The sums to get $Q_{i,j}$'s for $j<n$ eliminate one $z$ variable
at each step but do nothing to the degree in $x$ and $y$ variables.
Thus all $P_i$'s are of degree at most that of $P_0$ and all
$Q_{i,j}$'s are at most twice this.

\section{Comments on $\pspace$}

\begin{itemize}

\item This reduction shows that all $\pspace$ problems are
self-reducible.  This is not true for higher complexity classes.

\item Papadimitriu\footnote{Papadimitriou, C. H. ``Games against
  nature [PSPACE, new characterization]'' J. Comp. and
  Sys. Sci. Oct. 1985; 31(2): 288--301.} interpreted $\pspace$ as the complexity of
  games.  For example GO is $\pspace$-complete.  One player is the
  existential quantifier and the other is the universal quantifier:
  ``There is some move player one can make so that for every move
  player two makes, $\ldots$''  

  $\ip$ is the class of solitare games.  The verifier is kind stupid.
  It generats random numbers and makes sure the rules are followed.
  The prover is the player and tries to convince the verifier that it
  can win.  

  The result that $\ip=\pspace$ shows that for almost any two player
  game (we don't quite know about Chess for example) there exists a
  solitare game which is just as ``intellectually stimulating''
  (complex).  The solitare game Mah-Jongg was shown to be
  $\pspace$-hard\footnote{Condon, A.; Feigenbaum, J.; Lund, C.; Shor,
  P. ``Random Debaters and the Hardness of approximating stochastic
  functions'' SIAM Journal on Computing. April 1997; 26(2):
  369--400.}.
\end{itemize}

\section{Other Models of Proofs}
\subsection{Multiple Interactive Proofs: $\mip$}
Use more than one prover.  Provers do not have knowledge of the
discussions between the verifier and the other provers, but they may
collaborate before interactions begin (even based on the
input). Clearly $\ip\subseteq\mip$: we ignore the other provers.  The
other direction is not so clear.

It was known for a long time that $\mip\subseteq \nexp$.  For the
inclusion $\nexp\subseteq\mip$, the basic idea is that
$\nexp$-complete problems may be phrased as: ``Does there exist a
$P_0$ such that $P_L(z)=a$ in a straightline program of polynomials?''
With multiple provers, we go through the usual interaction to get a
question of the form: ``Does $P_0(z_0)=a_0$?''  Then we ask this of
the second prover.

\subsection{Oracle Interactive Proof}
In this case, the prover is an oracle with no memory of past
interactions.  It was shown that $\mip\subseteq\oip\subseteq 2\ip$.
The power of having many provers may be simulated by having only two.

\subsection{Probabilistically Checkable Proofs (PCP's)}

\subsubsection{Definintion of $\pcp[r,q]$}

We use an oracle to examine some string $y$ that could be a
certificate for the statement $x\in L$.  We can only check a certain
number of bits of the certificate $y$ and only flip a certain number
of coins.  $L\in\pcp[r,q]$ if there exists a verifier $v$
of $x\in L$ such that
\begin{itemize}
\item $v$ tosses at most $r(|x|)$ coins
\item $v$ queries the certificate oracle in at most $q(n)$ bits
\item $v$ runs in polynomial time and accepts with probability
\begin{itemize}
\item $1$ if $x\in L$
\item $\le 1/2$ if $x\not\in L$
\end{itemize}
\end{itemize}

\subsubsection{Examples}
Let $|x|=n$.
\begin{itemize}
\item $\pcp[0,\poly(n)] = \np$
\item $\pcp[\poly(n),0] = \corp$
\item $\pcp[\poly(n),\poly(n)] = \nexp$ (non-trivial to
  prove)\footnote{Babai, L.; Fortnow, L.; Lund, C. ``Non-determinstic
  exponential time has two-prover interactive protocols.''
  Computational Complexity. 1991; 1(1): 3--40.}
\item $\pcp[O(\log(n)),O(1)]=\np$\footnote{Arora, S.; Safra, S. 1992.
  ``Probabilistic checking of proofs:  A new characterization of NP.''
  {\it Proceedings of the 33rd IEEE Symposium on Foundations of
  Computer Science}.  IEEE, New York, pp. 2--12.}
\item $\pcp[O(\log(n)),3] = \np$  This is hard to
  show\footnote{Guruswami, V. et al. ``A tight characterization of NP
  with 3 query PCPs.'' {\it Proceedings 39th Annual Symposium on
  Foundations of Computer Science}.  1998: 8--17.

  Hastad, J. ``Some optimal inapproximability results.'' In Proceedings of
  the 29th ACM Symposium on the Theory of Computation, 1997: 1--10.}.
\end{itemize}

\subsubsection{Begin discussion of a $\pcp[O(\log(n)),3]$ 
  verifier for $\np$.}

We can make a table of random bits and questions we want to ask about
the proof $y$ when the corresponding random bits come up.
$$
\begin{array}{cl}
\hbox{Bits}&\hbox{Rule}\\
000\cdots00&y_1=1\Rightarrow y_2=y_{20}\\
000\cdots01&y_1=0\Rightarrow y_{32}\vee \bar y_{100}\\
111\cdots11&\hbox{if $y_2=1$ then $y_3=y_4$ else $y_{10}=y_1$}\\
\end{array}
$$ Each question may be written as an eight clause CNF formula in at
most seven variables (we can only check three for any particular
evaluation).  We can arrange it so that seven of the eight clauses are
satisfied for any assignment of the variables.  Combine the CNF
clauses from all the rules into one forumal with $8M$ clauses.  By
definition of a $\pcp$, at least half the tests will not be satisfied
if the proof $y$ is bogus (not valid).  Thus $\le
(8M/2)+(7M/2)=15M/2=(15/16)8M$ clauses are satisfied for the
certficate $y$ of any $x\not\in L$.  We go over this discussion in
more detail next lecture and use the result to prove that no
$(16/15+\epsilon)$-approximation (see definition in next lecture) exists for
SAT.


\end{document}