\documentclass[11pt, a4paper]{article} \usepackage{../mysty} \renewcommand{\lesson}{12} \renewcommand{\lessontitle}{$\ip=\ps$} \renewcommand{\fulltitle}{Lesson \lesson: \lessontitle} \usepackage{xr} \externaldocument{../lesson-10/2022b-cot-note-10} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% START DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \begin{document} \date{} %\thispagestyle{empty} \begin{center} {\Large {\bf \fulltitle}} \end{center} \vspace{0.5cm} \noindent {\bf Theme:} The equivalence between the class $\ip$ and $\ps$. \section{The verifier for the number of satisfying assignments of boolean formulas} Consider the following language $L_{\sharpsat}$: \begin{align*} L_{\sharpsat} & \defeq \left\{ \begin{array}{l|l} (\varphi,k) & \begin{array}{l} \text{$\varphi$ is a boolean formula}\\ \text{and $k$ is the number of its satisfying assignments (in binary)} \end{array} \end{array} \right\} \end{align*} We will describe its IP protocol. \paragraph*{The arithmetization of boolean formulas.} Let $\varphi(x_1,\ldots,x_n)$ be a boolean formula with variables $x_1,\ldots,x_n$. We first convert it into a multi-variate polynomial $\widetilde{\varphi}(x_1,\ldots,x_n)$ by replacing the operators $\wedge$, $\vee$ and $\neg$ as follows. \begin{align*} \neg \varphi_1 \qquad& \mapsto\qquad 1-\widetilde{\varphi_1} \\ \varphi_1 \ \wedge \ \varphi_2 \qquad& \mapsto\qquad \widetilde{\varphi_1} \cdot \widetilde{\varphi_2} \\ \varphi_1 \ \vee \ \varphi_2 \qquad& \mapsto\qquad 1- (1-\widetilde{\varphi_1}) \cdot(1- \widetilde{\varphi_2}) \end{align*} By a straightforward induction on $\varphi$, it is not difficult to show that $\varphi(\vb) =\widetilde{\varphi}(\vb)$, for every $\vb=(b_1,\ldots,b_n)\in \{0,1\}^n$. Thus, \begin{align*} \sharp\varphi \ = \ \sum_{x_1=0}^1\ \sum_{x_2=0}^1\ \cdots\ \sum_{x_n=0}^1 \ \widetilde{\varphi}(x_1,\ldots,x_n). \end{align*} \paragraph*{An intuitive description of the verifier for $L_{\sharpsat}$.} Let $(\varphi,k)$ be the input and $x_1,\ldots,x_n$ be the variables in $\varphi$. Let $d$ be the maximal degree of each variable in $\widetilde{\varphi}$. Let $\bbF$ be some finite field with size $\geq 3d$. Denote by $f_i(x_1,\ldots,x_i)$ the following polynomial: \begin{align*} f_i(x_1,\ldots,x_i) & \defeq\ \sum_{x_{i+1}=0}^1\ \cdots\ \sum_{x_n=0}^1 \ \widetilde{\varphi}(x_1,x_2,\ldots,x_n) \end{align*} In each round $i$, on some numbers $r_1,\ldots,r_i,t \in \bbF$, the prover tries to convince the verifier that the following holds. \begin{align} \label{eq:sharpsat-induction} f_i(r_1,\ldots,r_i) \ = \ t, \end{align} The protocol works by recursively on $i$. For each $1\leq i\leq n$, round $i$ works as follows Let $r_1,\ldots,r_{i-1}$ and $t$ be the values from the previous round and the prover tries to convince the verifier that the following holds. \begin{align} \label{eq:sharpsat-induction-b} f_{i-1}(r_1,\ldots,r_{i-1}) \ = \ t, \end{align} \begin{itemize} \item The verifier asks for the polynomial $f_{i}(r_1,\ldots,r_{i-1},x_{i})$. \item Suppose the prover replies with $g(x_{i})$. \item The verifier checks if the following holds. $$ t \ = \ g(0) + g(1) $$ Reject, if it does not. Otherwise, continue. \item The verifier chooses a random $r\in \bbF$ and proceeds to the next round to check: $$ g(r) \ = \ f_{i}(r_1,\ldots,r_{i-1},r). $$ \end{itemize} Note that in round~1 the value $t$ is $k$. In the last round $i=n$, the verifier can compute the value $f_{n}(r_1,\ldots,r_{n-1},r)$ directly. \paragraph*{A more precise description of the verifier for $L_{\sharpsat}$.} Let $(\varphi,k)$ be the input and $x_1,\ldots,x_n$ be the variables in $\varphi$. Let $d$ be the maximal degree of each variable in the polynomial $\widetilde{\varphi}(x_1,\ldots,x_n)$. Let $\bbF$ be some finite field with size $\geq 3d$. The verfiier works as follows, where all polynomial evaluation is computed in the field $\bbF$. \vspace{0.3cm} \noindent (Round~1) \begin{itemize} \item The verifier asks the prover for the polynomial $f_1(x_1)$. \item Suppose the prover replies with a polynomial $g_1(x_1)$. \item The verifier checks if $k=g_1(0)+g_1(1)$. If not, the verifier rejects immediately. Otherwise, continue. \end{itemize} \noindent (Round~2) \begin{itemize} \item The verifier randomly chooses a number $r_1\in \bbF$ and asks the prover for the polynomial $f_2(r_1,x_2)$. \item Suppose the prover replies with a polynomial $g_2(x_2)$. \item The verifier checks if $g_1(r_1)= g_2(0)+g_2(1)$. If not, the verifier rejects immediately. Otherwise, continue. \end{itemize} $\ldots$ and so on, where each round $i\leq n$ is as follows. \vspace{0.3cm} \noindent (Round~$i$) \begin{itemize} \item The verifier randomly chooses a number $r_{i-1}\in \bbF$ and asks the prover for the polynomial $f_i(r_1,\ldots,r_{i-1},x_i)$. \item Suppose the prover replies with a polynomial $g_i(x_i)$. \item The verifier checks if $g_{i-1}(r_{i-1})= g_i(0)+g_i(1)$. If not, the verifier rejects immediately. Otherwise, continue. \end{itemize} \noindent (Round~$n+1$) \begin{itemize} \item The verifier randomly chooses a number $r_{n}\in \bbF$. \item The verifier checks if $g_{n}(r_{n})= f_n(r_1,\ldots,r_n)$. It accepts if and only if the equality holds. Note that $f_n(r_1,\ldots,r_n)=\widetilde{\varphi}(r_1,\ldots,r_n)$. \end{itemize} \paragraph*{Proof of correctness.} Note that if $(\varphi,k)\in L_{\sharpsat}$, then the protocol works correctly. For each $r_1,\ldots,r_{i-1}$, the prover replies with $f_i(r_1,\ldots,r_{i-1},x_i)$. So, $\prarg {V \ \text{accepts}}=1$. Suppose $(\varphi,k)\notin L_{\sharpsat}$. That is, \begin{align*} k \ \neq \ \sum_{x_1=0}^1\ \sum_{x_2=0}^1\ \cdots\ \sum_{x_n=0}^1 \ \widetilde{\varphi}(x_1,\ldots,x_n). \end{align*} We can assume that in round $1$ the prover replies with a polynomial $g_1(x_1)$ where $k=g_1(0)+g_1(1)$. Otherwise, verifier rejects immediately. Note that this means that $g_1(x_1)\neq f_1(x_1)$. We will calculate the probability that $V$ rejects. Consider a fixed interaction between a prover and the verifier. Let $r_1,\ldots,r_n$ be the random strings generated by the verifier. There are two scenarios. \begin{enumerate}[(S1)] \item $g_n(x_n) \neq f_n(r_1,\ldots,r_{n-1},x_n)$. \item $g_n(x_n) = f_n(r_1,\ldots,r_{n-1},x_n)$. \end{enumerate} That is, in (S1) the polynomial $g_n(x_n)$ sent by the prover is not ``correct'' whereas in (S2) $g_n(x_n)$ is correct. In (S1) the probability that the verifier accepts in round $n+1$ is: $$ \prdist {r_n} {V \ \text{accepts}}\ =\ \prdist {r_n} {g_n(r_n)=f_n(r_1,\ldots,r_n)}\ \leq\ \frac{d}{|\bbF|}\ \leq\ \frac{1}{3} $$ The second last inequality comes from the fact that the degree of $g_n$ and $f_n$ are at most $d$, hence, there at most $d$ such $r_n$ where $g_n(r_n)= f_i(r_1,\ldots,r_{n-1},r_n)$. We now consider (S2). Since $g_1(x_1)\neq f_1(x_1)$ and $g_n(x_n) = f_n(r_1,\ldots,r_{n-1},x_n)$, there is $1\leq i \leq n$ such that: $$ g_{i-1}(x_{i-1})\neq f_{i-1}(r_1,\ldots,r_{i-2},x_{i-1}) \qquad\text{and}\qquad g_i(x_i) = f_i(r_1,\ldots,r_{i-1},x_i) $$ The probability that the verifier continues in round $i$ is: \begin{align*} \prdist {r_{i-1}} { \text{the verifier continues in round} \ i } &\ = \ \prdist {r_{i-1}} { g_{i-1}(r_{i-1})= g_{i}(0)+g_{i}(1) } \\ &\ = \ \prdist {r_{i-1}} { g_{i-1}(r_{i-1})= f_{i-1}(r_1,\ldots,r_{i-1}) } \\ &\ \leq \ \frac{d}{|\bbF|}\ \leq\ \frac{1}{3} \end{align*} Again, the second last inequality is due to the degree of $g_n$ and $f_n$ being at most $d$. In both scenarios (S1) and (S2), the probability that the verifier rejects is $\geq 2/3$. Thus, we have shown the IP protocol for the language $L_{\sharpsat}$. We state this result formally. \begin{theorem} \label{theo:sharpsat-ip} {\bf (Lund, Fortnow, Karloff, Nisan 1990)} $L_{\sharpsat}\in \ip$. \end{theorem} \begin{corollary} \label{theo:ph-ip} $\pht\subseteq \ip$. \end{corollary} \section{The verifier for $\tqbf$} We will now describe the IP protocol for $\tqbf$. The idea is simple. To verify that $\forall x\ \varphi(x)$ is true, we check that $\widetilde{\varphi}(0)\cdot \widetilde{\varphi}(1)\neq 0$. Likewise, to verify that $\exists x\ \varphi(x)$ is true, we check that $1- (1-\widetilde{\varphi}(0)) \cdot (1- \widetilde{\varphi}(1))\neq 0$. We formalize this intuition as follows. Let $q(\vx,y_1,\ldots,y_n)$ be a polynomial where $\vx$ is a vector of variables and $y_1,\ldots,y_n$ are variables. The expression $\sQ_1 y_1\cdots \sQ_n y_n\ q(\vx,y_1,\ldots,y_n)$, where each $\sQ_i \in \{\sA,\sE\}$, defines a polynomial $p(\vx)$ as follows. \begin{itemize} \item If $\sQ_1 = \sA$: \begin{align*} p(\vx) & \ \defeq \ \Big(\sQ_2y_2 \cdots \sQ_n y_n \ q(\vx,0,y_2,\ldots,y_n)\Big)\cdot \Big(\sQ_2y_2 \cdots \sQ_n y_n \ q(\vx,1,y_2,\ldots,y_n)\Big) \end{align*} \item If $\sQ_1 = \sE$: \begin{align*} p(\vx) & \ \defeq \ 1 - \Big(1- \sQ_2y_2 \cdots \sQ_n y_n \ q(\vx,0,y_2,\ldots,y_n)\Big)\cdot \Big(1- \sQ_2y_2 \cdots \sQ_n y_n \ q(\vx,1,y_2,\ldots,y_n)\Big) \end{align*} \end{itemize} Intuitively, the IP protocol for $\tqbf$ works as follows. Let $\Psi \defeq Q_1x_1\cdots Q_nx_n\ \varphi(x_1,\ldots,x_n)$ be the input QBF. Its arithmetization is $\widetilde{\Psi} \defeq \sQ_1x_1\cdots \sQ_nx_n\ \widetilde{\varphi}(x_1,\ldots,x_n)$, where each $\forall x_i$ is replaced by $\sA x_i$ and each $\exists x_i$ by $\sE x_i$. It is not difficult to show that $\Psi$ is true QBF if and only if $\widetilde{\Psi}=1$. Checking whether $\widetilde{\Psi}=1$ can be done by similar method in the previous section. In each round $i$ the verifier asks the prover for the polynomial: \begin{align*} f_i(r_1,\ldots,r_{i-1},x_i) &\ \defeq \ \sQ_{i+1} x_{i+1} \cdots \sQ_n x_n \ \widetilde{\varphi}(r_1,\ldots,r_{i-1},x_i,x_{i+1},\ldots,x_n) \end{align*} for some randomly chosen numbers $r_1,\ldots,r_{i-1}$. However, note that the degree of $x_i$ can be $2^{n-i}$. For this, we introduce a new operator $\sL x$, whose semantics is defined as follows. The expression $\sL z \sQ_1 y_1 \cdots \sQ_n y_n\ q(\vx,z,y_1,\ldots,y_n)$ defines the following polynomial $p(\vx,z)$: \begin{align*} p(\vx,z) & \ \defeq \ (1 - z) \sQ_1y_1 \cdots \sQ_n y_n \ q(\vx,0,y_1,\ldots,y_n) \ + \ z \sQ_1y_1 \cdots \sQ_n y_n \ q(\vx,1,y_1,\ldots,y_n) \end{align*} In the expression $\sL z \sQ_1 y_1 \cdots \sQ_n y_n\ q(\vx,z,y_1,\ldots,y_n)$, the variables $\vx$ and $z$ are free variables. The operator $\sL z\ q(\vx,z)$ means ``linearize'' the variable $z$ in the polynomial $q(\vx,z)$. Since in the operators $\sA$ and $\sE$ we are only evaluating the polynomial on $0$ and $1$ and $x^k = x$ for $x\in \{0,1\}$, the value $\sQ_{1} x_{1} \cdots \sQ_n x_n \ \widetilde{\varphi}(x_1,\ldots,x_n)$ is equal to: \begin{align} \label{eq:tqbf-arithmetic} \sQ_{1} x_{1} \sL x_1\ \sQ_2 x_2 \sL x_1 \sL x_2\ \cdots\ \sQ_n x_n \sL x_1 \cdots \sL x_{n} \ \widetilde{\varphi}(x_1,\ldots,x_n) \end{align} The IP protocol will verify that the value in Eq.(\ref{eq:tqbf-arithmetic}) is $1$. It works recursively where in each round $i$, on some numbers $r_1,\ldots,r_k$ and $t$, the prover tries to convince the verifier that the following holds. \begin{align} \label{eq:tqbf-induction} \sQ_{i} z_i \cdots \sQ_m z_m \ \widetilde{\varphi}(r_1,\ldots,r_k,x_{k+1},\ldots,x_n) \ = \ t, \end{align} where $x_{k+1},\ldots,x_n$ are the variables quantified by $\sA$ or $\sE$ in $\sQ_iz_i \cdots \sQ_mz_m$. In round~0, the prover ``tells'' the verifier that the value in~(\ref{eq:tqbf-arithmetic}) is $1$. Otherwise, the verifier rejects immediately. In round $i$, suppose the values $r_1,\ldots,r_k$ and $t$ are already given. The verifier tries to verify that (\ref{eq:tqbf-induction}) is true as follows. \begin{itemize} \item If $\sQ_i z_i$ is $\sA x_{k+1}$. The verifier asks for the polynomial: $$ \sQ_{i+1} z_{i+1} \cdots \sQ_m z_m \ \widetilde{\varphi}(r_1,\ldots,r_k,x_{k+1},\ldots,x_n) $$ Suppose the prover replies with $g(x_{k+1})$. The verifier checks the following. $$ t\ =\ g(0)\cdot g(1) $$ Reject, if it does not hold. Otherwise, continue. The verifier chooses a random number $r\in \bbF$ and proceeds to the next round to verify: $$ g(r) \ = \ \sQ_{i+1} z_{i+1} \cdots \sQ_m z_m \ \widetilde{\varphi}(r_1,\ldots,r_k,r,x_{k+2},\ldots,x_n) $$ \item If $\sQ_i z_i$ is $\sE x_{k+1}$. Similar to above, but the verifier checks the following. $$ t\ =\ 1- (1-g(0))\cdot (1-g(1)) $$ \item If $\sQ_i z_i$ is $\sL x_j$, for some $1\leq j \leq k$. The verifier asks for the polynomial: $$ \sQ_{i+1} z_{i+1} \cdots \sQ_m z_m \ \widetilde{\varphi}(r_1,\ldots,r_{j-1},x_j,r_{j+1},\ldots,r_k,x_{k+1},\ldots,x_n) $$ Suppose the prover replies with $g(x_{j})$. The verifier checks the following. $$ t \ =\ (1-r_j)g(0) + r_j g(1) $$ Reject, if it does not hold. Otherwise, continue. The verifier chooses a random number $r\in \bbF$ and proceeds to the next round to verify: $$ g(r) \ = \ \sQ_{i+1} z_{i+1} \cdots \sQ_m z_m \ \widetilde{\varphi}(r_1,\ldots,r_{j-1},r,r_{j+1},\ldots,r_k,x_{k+1},\ldots,x_n) $$ \end{itemize} \begin{theorem} {\bf (Shamir 1990)}. $\tqbf \in \ip$. Hence, $\ip=\ps$. \end{theorem} \begin{theorem} If $\ps \subseteq \ppoly$, then $\ps =\ma$. \end{theorem} \end{document} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%% END OF DOCUMENT %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%