$$\# \mathrm{SAT} \in \mathrm{IP}$$#

#SAT problem#

Definition 4 (#SAT)

Let $$\phi$$ be any Boolean formula on $$n$$ variables of size $$S=\operatorname{poly}(n)$$ The goal of #SAT is to compute the number of satisfying assignments of $$\phi$$ :

$\sum_{x \in\{0,1\}^{n}} \phi(x)$

The interactive proof for #SAT#

Definition 5 (arithmetization)

The process of replacing the Boolean formula $$\phi$$ with an arithmetic circuit $$\psi$$ computing an extension polynomial $$g$$ of $$\phi$$.

We can turn $$\phi$$ into an arithmetic circuit $$\psi$$ over $$\mathbb{F}$$ that computes the desired extension $$g$$ of $$\phi$$.

• For any gate in $$\phi$$ computing the AND of two inputs $$y, z, \psi$$ replaces $$\operatorname{AND}(y, z)$$ with multiplication of $$y$$ and $$z$$ over $$\mathbb{F}$$. It is easy to check that the bivariate polynomial $$y \cdot z$$ extends the Boolean function $$\operatorname{AND}(y, z)$$, i.e., $$\operatorname{AND}(y, z)=y \cdot z$$ for all $$y, z \in\{0,1\}$$.

• Likewise, $$\psi$$ replaces any gate computing $$\operatorname{OR}(y, z)$$ by $$y+z-y \cdot z$$.

• Any formula leaf of the form $$\bar{y}$$ (i.e., the negation of variable $$y$$ ) is replaced by $$1-y$$

It is easy to check that $$\psi(x)=\phi(x)$$ for all $$x \in\{0,1\}^{n}$$, and that the number of gates in the arithmetic circuit $$\psi$$ is at most $$3 S$$.

Then apply the sum-check protocol to compute $$\sum_{x \in\{0,1\}^{n}} g(x)$$