We are here to prove a theorem.
The number of satisfying assignments is a problem solvable in IP(k).
Consider some 3SAT formula:
\begin{equation} \phi\qty(x) = \qty(x_1 \vee x_3 \vee \neg x_9) \wedge \qty(\neg x_2 \vee \neg x_5 \vee x_{50}) \wedge \dots \end{equation}
where \(\phi\qty(x)\) has exactly \(k\) satisfying assignments. This expression has \(n\) variables and \(m\) clauses. Notice that: \(x_1 \vee x_3 \vee \neg x_{9}\) if and only if \(x_1 = 0, x_3 = 0, x_{9} = 1\). This has the following properties:
- \(\qty(1 - x_1) \qty(1 - x_3) x_{9} = 1\) if \(x_1 \vee x_3 \vee \neg x_{9}\) false
- \(1-\qty(1 - x_1) \qty(1 - x_3) x_{9} = 1\) if \(x_1 \vee x_3 \vee \neg x_{9}\) true
This is a polynomialization of \(\phi\)
We can now say the following things; for \(\phi\) , we have:
For a polynomialization \(q\qty(x)\) of \(\phi\), we have
\begin{equation} \forall x \in \qty {0,1}^{n}, q\qty(x) =1, \text{if x SAT } \phi, q\qty(x) = 0 \end{equation}
the degree of \(q\) is at most \(3m\) for \(m\) clauses
…so any poly-time machine can build \(q\) itself
But! Using \(q\) is actually hard for a poly-time machine; to compute the number of satisfying assignments for \(n\) variables, we can try everything:
\begin{equation} q_{\#sat} = \sum_{b_1=0}^{1} \sum_{b_2=0}^{1} \dots \sum_{b_2=k}^{1} q\qty(b_1, b_2, \dots, b_{n}) = k \end{equation}
but this is exptime. Now, consider the computation above, with prime \(p\) with at least \(2n\) many digits:
\(q_{\#SAT}\) is true IFF \(q\) is true mod \(p\)
because
Now, consider the following BIG BRAIN move:
consider the univariate polynomial:
\begin{equation} r\qty(x_1) = \sum_{b_2 = 0}^{1} \sum_{b_3 = 0}^{1} \dots \sum_{b_n = 0}^{1} q\qty(x_1, b_2, \dots, b_{n}) \end{equation}
\(q_{\# \text{SAT}} \ \text{mod}\ p\) is true IFF \(r\qty(0) + r\qty(1) = k \ \text{mod}\ p\)
Can we evaluate this, then? As is, no, but notice that
\(r\) is a urinary polynomial of degree \(\leq 3m\), and hence has an expression of the form:
\begin{equation} r’ \qty(x_1) = c_0 + c_1 x_1 + c_2 x_1^{2} + \dots \end{equation}
by just expanding \(q\), we get a univariate expression one to expand to \(n\). The beneficent is that we don’t have to factor the whole thing out, we just have to plug in values.
So suppose our prover generates an \(r’\) of this shape, send \(\ \text{mod}\ p\) of it back (since otherwise coefficients may get too large), our prover must show that \(r’\) behaves just like \(r\).
That is, “if you claim that \(r’\) is \(r\), then you must be claiming that”: \(r\qty(a) = r’\qty(a)\).
clearly there is an accepting strategy, but if the original \(q_{\# \text{SAT}}\) is false,