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.



an algebraic variety for a boolean circuit
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*](http://www.jmilne.org/math/CourseNotes/lec.html), 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](https://math.stackexchange.com/questions/118040/connected-components-of-a-scheme-are-irreducible)).


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.


