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





