Starting with a simple observation. If $x,y\in\{0,1\}$, then the arithmetic product $x\cdot y$ corresponds to the logical conjunction if we interpret $1$ as *true* and $0$ as *false*.

But then, for a generic propositional logic formula $\phi$ in $n$ variables, we can obtain a polynomial $f(\phi)$ as follows:

\begin{align}
f(p) & = x\_p \\
f(\neg \phi) & = 1 - f(\phi) \\
f(\phi\_1\land\phi\_2) &= f(\phi\_1)\cdot f(\phi\_2) \\
f(\phi\_1\lor\phi\_2) &= f(\neg(\neg\phi\_1\land\neg\phi\_2)) \\
 &= 1-((1-f(\phi\_1))(1-f(\phi\_2)))
\end{align}

Then if $f(\phi)=1$ has integer solutions in $[0,1]^n$, the formula is satisfiable.

For example, if $\phi\equiv p\to q\equiv\neg p \lor q$, then $f(\phi)=x\_px\_q-x\_p+1$, and indeed $x\_px\_q-x\_p+1=1$ holds for $x\_p=0$ and for $x\_q=1$.

So, finding this kind of roots of polynomials is NP-hard, as interesting as this might be.

My question risks to be too vague, but has this been used in NP-hardness proofs for some more interesting algebraic problem?

Is this connection between propositional formulas and polynomials (hence between SAT and algebra) useful for anything?