\documentclass[12pt]{article}
\input{preamble}
\begin{document}
\newcommand{\nppoly}{NP/$poly $} %% NP/Poly shorthand
\lecture{17}{April 13, 1999}{Daniel A. Spielman}{Navid Sabbaghi}
Today we study a new topic: Interactive Proofs.
Interactive proofs were motivated by the question: what models
allow us to be convinced of membership of a word in a language
with high probablity? Interactive proofs are a model for achieving
that conviction through communication rather than the mere
presentation of a proof. In this lecture we will be interested
in seeing what the power of this model is (what classes of languages
that we are already familiar with, are included in it?).
\section{Interactive Proofs}
So what are Interactive proofs? Imagine two parties and the conversation
between them. One party is an ''all-powerful'' \emph{Prover}, which we denote by $P$. The Prover is a prodigy and has unlimited computational resources
and more formally can be defined by an arbitrary function. The second
party is the \emph{Verifier, }which we denote by $V$. The Verifier is a
polynomial time Turing Machine, which has access to randomness in the sense
that it can toss coins and ask different questions depending on the
outcome. The coins are kept \emph{private} to the Verifier. The conversation
is a sequence of ''questions'' from $V$ and ''answers'' from $P$ in which
the Prover is trying to convince the Verifier of some statement by answering
the Verifier's questions. The questions and answers are restriced to being
polynomial in the length of the input.
Why do we choose these constraints? Does this model make sense? Well
it is essential that $V$ has access to randomness because otherwise we will
never escape $NP$. In the absence of randomness available to $V$, $P$ can
predict exactly what $V$ will ask and precompute the whole sequence of
questions and answers, so in fact the interaction
would not be needed. If $V$ can toss
coins, however, $P$\ cannot predict what the question is going to be.
What are some examples of this protocol? A simple example of
an interactive proof is a protocol for convincing a
colorblind friend that colors exist. The protocol is: you, the Prover, get two
balls of different colors (say red and blue) which are otherwise identical.
You give the balls to your colorblind friend, the Verifier, and tell him
that he has a red ball in his right hand and a blue ball in his left hand.
The friend, the Verifier, then hides the balls behind his back and randomly
shuffles them, so that he knows which ball is in which hand but you don't.
He then shows them to you and you correctly identify the balls. Therefore
the friend, the Verifier, will be convinced of the existence of colors
with high probability. Graph Non-Isomorphism is another problem that
is can be solved with an interactive proof.
\subsection{Interactive Proof Example: Graph Non-Isomorphism}
We first define Isomorphism of graphs: two graphs G and H are isomorphic if
one is a permutation of the other. More formally,
\begin{definition}
Two graphs $G$ and $H$ are \textbf{isomorphic} if
\begin{itemize}
\item
G and H have the same number of nodes n,
\item
$\exists$ a permutation $\pi$ of vertices of graph G such that
edge ($\pi$(i),$\pi$(j)) $\in$ G $\iff$ edge (i,j) $\in$ H.
\end{itemize}
\end{definition}
Now proving that graphs are isomorphic is easy. A ``proof'' of isomorphism
is simply the permutation, $\pi$. But think about how one would prove
that two graphs are \emph{not} isomorphic. That problem has been approached
deterministically using ideas from group theory and the best time bound so
far for the general graph non-isomorphism problem is
TIME($2^{O(\sqrt{n})}$). If we restrict the class of graphs to say bounded
degree graphs, polynomial algorithms do exist, but still they are very
far from trivial. At any rate, we will see that there is a simple Interactive
Proof for the graph nonisomorphism problem.
The simple interactive proof is very similar to convincing a colorblind friend
that colors exists. Say you (the friend, verifier) are given two graphs G
and H. You can put them behind your back and mix them up and pull one out and
ask the prover ``is this graph the one that was originally in my left or
right hand?'' If they are indeed isomorphic (ie the same graph) then the
prover should not be able to tell which one is which.
More formally, we define $NONISO$\ as a language of all pairs of
graphs $(G,H)$ such that $G$ and $H$ are \textbf{not} isomorphic.
We now give an interactive proof for $NONISO.$ We specify the protocol by
which $P$ will convince $V$ that two graphs $G$ and $H$ are non-isomorphic.
We assume that $G$ and $H$ have the same number of vertices, since
otherwise the graphs are obviously non-isomorphic. Let $n$ denote the number
of vertices of either graph.
The IP Protocol
\begin{enumerate}
\item VERIFIER: Flip a random bit $b\in \{0,1\}$; $b$ is a ''fair'' coin with
probability $1/2$ of either outcome. This will decide which
graph the verifier will ``play'' with.
\item VERIFIER: Choose a random
permutation $\pi $ of the verticies $\{1,2,...n\}.$ If
$b=0$ show the Prover $\pi
(G).$ Otherwise show $\pi (H)$
\item PROVER: In response the Prover says which graph is being shown to it.
\item VERIFIER: If the prover is correct, then accept, else reject.
\end{enumerate}
This can be repeated as many times as needed to boost confidence. As long as
the prover guesses correctly, the verifier should become
more confident that graphs are non-isomorphic.
\textbf{Proof of Correctness}.
We use notation $(V,P)$\ to denote the outcome of the protoocol.
If $G$ is not isomorphic to $H$ then there exists a prover $P$ s.t. $Pr[(V,P)
$ accept$]=1$
If $G$ is isomorphic to $H$, then for any P,
on $k$ runs of the protocol $Pr[(V,P)$
accept$] \leq \frac 1{2^k}.$ The latter is because $P$\ cannot distinguish
between two isomorphic graphs.
\subsection{Formal definitions}
So now in this section we will formalize the notion of an Interactive
Proof.
In general, the key elements of an Interactive Proof are
\begin{enumerate}
\item players $V$ and $P$ take turns
\item after a certain number of turns they stop and $V$ decides whether to
accept or reject.
\end{enumerate}
We can define $V$ as a function $V(w,r,C)\rightarrow \{S,accept,reject\},$
where $w$ is an input string, $r$ is a random string and $C$ and $S$ are
strings denoting respectively the conversation so far and $V$'s response.
More specifically, the output of this function is defined as follows:
if $C=\varepsilon $ output $S=V_1$
if $C=V_1,P_1,...V_i,P_i$ and $i