5
$\begingroup$

There is a polynomial reduction from a $3-CNF$ $SAT$ problem to some system of polynomial equations over $\mathbb{F}_2$.

I mean there is polynomial reduction $F$ such that for every boolean circuit $g(x_1,\ldots, x_n)$ the corresponding system of polynomial equations $F(g) = \begin{cases} f_1(x_1, \ldots, x_n)=0 \\ \ldots \\ f_m(x_1, \ldots, x_n)=0 \end{cases} $

satisfies the following property: $ \forall (x_1, \ldots, x_n) \in \mathbb{F}_2^n: g(x_1, \ldots, x_n)=1 \Leftrightarrow (x_1,\ldots, x_n)$ is the solution of $F(g)$.

So, every boolean circuit corresponds to an algebraic set. To use power of algebraic geometry we wish this set has some nice properties. Is there a polynomial reduction such that every circuit corresponds to an absolute irreducible algebraic set?

UPD: in fact it is also interesting to find answers on weaker questions: is there a reduction to an algebraic variety with poly$(n)$ equations, can this reduction be calculated by using poly$(n)$ memory and so on.

$\endgroup$
  • $\begingroup$ (1) The property you wrote down is much stronger than just NP-completeness of the problem. It happens to be true for 3-CNF, but for general circuits, it only works under a generous representation of the polynomials $f_i$ (say, as arithmetic circuits). NP-completeness only says there is a poly-time transformation of circuits $g(x_1,\dots,x_n)$ to systems of polynomials $f_i(y_1,\dots,y_m)$ so that $g$ is satisfiable iff the polynomial system is solvable, without any implied connection between the two solution sets. Do you allow this or not? $\endgroup$ – Emil Jeřábek Apr 24 '16 at 14:34
  • $\begingroup$ (2) When you write "irreducible", do you mean irreducible over $\mathbb F_2$, or absolutely irreducible? $\endgroup$ – Emil Jeřábek Apr 24 '16 at 14:35
  • $\begingroup$ (3) As for the update: satisfiability can be determined by itself in poly(n) space, and then you can just output a fixed solvable or unsolvable polynomial system according to the result. $\endgroup$ – Emil Jeřábek Apr 24 '16 at 14:38
  • $\begingroup$ (1) yes, I understand that my property is stronger but we can do this transformation for a 3-cnf formula $\endgroup$ – Alexey Milovanov Apr 24 '16 at 15:02
  • $\begingroup$ (2)I want an absolutely irreducible variety $\endgroup$ – Alexey Milovanov Apr 24 '16 at 15:12
5
$\begingroup$

Are you willing to allow adding additional coordinate variables $y_1,\ldots,y_m$ that are unused in $g$? (I mean that, for any $x_1,\ldots,x_n,y_1,\ldots,y_m \in \mathbb{F}_2$, the variety will have the $\mathbb{F}_2$-point $(x_1,\ldots,x_n,y_1,\ldots,y_m)$ iff $g(x_1,\ldots,x_n)=1$. Note that I am asserting the equivalence for an abitrary value of the $y_j$, not just with the existence of such a value: so it is enough if I have an unlimited supply of unused variables to draw from.)

If so, the following can be done: find $f_1,\ldots,f_m \in \mathbb{F}_2[x_1,\ldots,x_n]$ as you described. We can assume that the $f_j$ have degree at most $1$ in each variable and are linearly independent over $\mathbb{F}_2$. Define $\widehat{f_j} \in \mathbb{F}_2[x_1,\ldots,x_n,y_1,\ldots,y_m]$ by $\widehat{f_j} := y_j^2 - y_j - f_j$ (the minus signs are purely decorative here, of course, and are merely there to emphasize that this is an Artin-Schreier equation). Since for $z\in\mathbb{F}_2$ the equation $y^2 - y - z = 0$ in the unknown $y$ over $\mathbb{F}_2$ has a solution iff $z=0$, in which case it has both $y=0$ and $y=1$, the variety $V := \{(\forall j) \widehat{f_j}=0\}$ defined by the $\widehat{f_j}$ has the property I stated above. It remains to determine whether it is absolutely irreducible.

Now the morphism from $V$ to $\mathbb{A}^n$ consisting of projecting to the first $n$ coordinates is étale. This is simply by the Jacobian criterion: $\frac{\partial}{\partial y_j}\widehat{f_{j'}} = \delta_{j,j'}$ (with $\delta_{j,j}=1$ and $\delta_{j,j'}=0$ if $j\neq j'$, of course). See, e.g., Milne's Lectures on Étale Cohomology, prop. 2.1. In particular, $V$ is smooth (or just use the Jacobian criterion directly for smoothness), so to show that it is geometrically integral, it is equivalent to show that it is geometrically connected (see, e.g., here).

Now this in turn is equivalent to the field extension $L = K(y_1,\ldots,y_m)$ of $K := k(x_1,\ldots,x_n)$ (where $k$ is the algebraic closure of $\mathbb{F}_2$) generated by the equations $y_j^2 - y_j - f_j$ being of the right degree (namely, $2^m$). But these equations are Artin-Schreier equations, and by Artin-Schreier theory (Lang, Algebra, chapter VI theorem 8.3), it is enough for the $f_j$ to be $\mathbb{F}_2$-linearly independent with a span in direct sum with $\wp K := \{h^2-h : h\in K\}$. But since we assumed that the $f_j$ were $\mathbb{F}_2$-linearly independent and their span consists entirely of polynomials of degree $<2$ in each variable, which are certainly not in $\wp K$ except for zero, this is indeed the case.

$\endgroup$
  • $\begingroup$ I allow new variables in your solution because there is a direct connection between $\mathbb{F}_2$-points $(x_1, \ldots, x_n, y_1, \ldots, y_m$ in new system and $\mathbb{F}_2$-points $(x_1, \ldots, x_n)$ in the original system. Thank you very much, this is wonderful! $\endgroup$ – Alexey Milovanov Apr 27 '16 at 19:43
  • $\begingroup$ Does the same argument work if change $f_j$ to $\hat f_j := y_j(f_j + 1) + 1$ and so this set has $\mathbb{F}_2$-point iff $(x_1, \ldots, x_n)$ is rational solution in the original system and all $y_i$ are equal to $1$? $\endgroup$ – Alexey Milovanov Apr 28 '16 at 9:13
  • 1
    $\begingroup$ @Alexey Yes, that also works: you get a variety that is isomorphic to an open set (namely $\{(\forall j)\,f_j\neq 1\}$) of $\mathbb{A}^n$, hence also smooth and geometrically irreducible like the one I proposed. The main difference with the one I proposed is you get the equivalence with only a specific value of the $y_j$, not with any; but if that's fine with you, of course, it's simpler. $\endgroup$ – Gro-Tsen Apr 28 '16 at 13:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.