\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}