SU-CS254 FEB262025 — Jemoka Knowledge Base

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\left(x\right) = \left(x_1 \vee x_3 \vee \neg x_9\right) \wedge \left(\neg x_2 \vee \neg x_5 \vee x_{50}\right) \wedge \dots \end{equation}

where \phi\left(x\right) 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: \left(1 - x_1\right) \left(1 - x_3\right) x_{9} = 1 if x_1 \vee x_3 \vee \neg x_{9} false 1-\left(1 - x_1\right) \left(1 - x_3\right) 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\left(x\right) of \phi, we have

\begin{equation} \forall x \in \left\{0,1\right\}^{n}, q\left(x\right) =1, \text{if x SAT } \phi, q\left(x\right) = 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\left(b_1, b_2, \dots, b_{n}\right) = 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\left(x_1\right) = \sum_{b_2 = 0}^{1} \sum_{b_3 = 0}^{1} \dots \sum_{b_n = 0}^{1} q\left(x_1, b_2, \dots, b_{n}\right) \end{equation}

q_{\# \text{SAT}} \ \text{mod}\ p is true IFF r\left(0\right) + r\left(1\right) = 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’ \left(x_1\right) = 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\left(a\right) = r’\left(a\right). clearly there is an accepting strategy, but if the original q_{\# \text{SAT}} is false,