Suggest edit — SU-CS254 FEB262025

Title

Name

Note

---
title: "SU-CS254 FEB262025"
source: https://www.jemoka.com/posts/kbhsu_cs254_feb262025/
date: 2025-02-26
---

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
&hellip;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&rsquo; \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&rsquo;t have to factor the whole thing out, we just have to plug in values.
So suppose our prover generates an \(r&rsquo;\) of this shape, send \(\ \text{mod}\ p\) of it back (since otherwise coefficients may get too large), our prover must show that \(r&rsquo;\) behaves just like \(r\).
That is, &ldquo;if you claim that \(r&rsquo;\) is \(r\), then you must be claiming that&rdquo;: \(r\qty(a) = r&rsquo;\qty(a)\).
clearly there is an accepting strategy, but if the original \(q_{\# \text{SAT}}\) is false,