This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note though that the system is represented in non-trivial manner). The reason it is OK to consider more than one equation is because the conjunction of the conditions $f_i(x_1 ... x_n) = 0$ is equivalent to the single condition $\prod_i (f_i(x_1 ... x_n) + 1) + 1 = 0$.

• This reminds of the solution of Hilbert's 10th problem, namely that it is undecidable whether a system of polynomial equations over $\mathbb{Z}$ has roots. Is there a formal relation? Can we use the undecidability over $\mathbb{Z}$ to provide clues why the problem is hard over $\mathbb{F}_2$ (that is, $P \ne NP$)? What is known about decidability and complexity for other rings? In particular, what is known about complexity over $\mathbb{F}_p$ for p prime > 2?

• The system of polynomial equations defines an algebraic scheme. Is it possible to find algebro-geometric conditions on this scheme, s.t. something can be told about the complexity of SAT restricted to such schemes?

• The solutions of our system of polynomial equations are the fixed points of the Frobenius endomorphism on the corresponding variety over $\bar{\mathbb{F}}_2$. There is a variant of Lefschetz's fixed-point theorem which relates the existence of such points to $l$-adic cohomology. Can this be used to provide some insight on P vs. NP?

EDIT: There is an especially appealing encoding of 3-SAT by algebraic varieties. Namely, write an equation of the form $(x + a)(y + b)(z + c) = 0$ for each clause, where $x, y, z$ are variables and $a, b, c \in \mathbb{F}_2$. This seems to yield a non-trivial variety in a natural way, so there's hope non-trivial insight can be obtained from applying algebro-geometric methods.

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note though that the system is represented in non-trivial manner). The reason it is OK to consider more than one equation is because the conjunction of the conditions $f_i(x_1 ... x_n) = 0$ is equivalent to the single condition $\prod_i (f_i(x_1 ... x_n) + 1) + 1 = 0$.

• This reminds of the solution of Hilbert's 10th problem, namely that it is undecidable whether a system of polynomial equations over $\mathbb{Z}$ has roots. Is there a formal relation? Can we use the undecidability over $\mathbb{Z}$ to provide clues why the problem is hard over $\mathbb{F}_2$ (that is, $P \ne NP$)? What is known about decidability and complexity for other rings? In particular, what is known about complexity over $\mathbb{F}_p$ for p prime > 2?

• The system of polynomial equations defines an algebraic scheme. Is it possible to find algebro-geometric conditions on this scheme, s.t. something can be told about the complexity of SAT restricted to such schemes?

• The solutions of our system of polynomial equations are the fixed points of the Frobenius endomorphism on the corresponding variety over $\bar{\mathbb{F}}_2$. There is a variant of Lefschetz's fixed-point theorem which relates the existence of such points to $l$-adic cohomology. Can this be used to provide some insight on P vs. NP?

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note though that the system is represented in non-trivial manner). The reason it is OK to consider more than one equation is because the conjunction of the conditions $f_i(x_1 ... x_n) = 0$ is equivalent to the single condition $\prod_i (f_i(x_1 ... x_n) + 1) + 1 = 0$.

• This reminds of the solution of Hilbert's 10th problem, namely that it is undecidable whether a system of polynomial equations over $\mathbb{Z}$ has roots. Is there a formal relation? Can we use the undecidability over $\mathbb{Z}$ to provide clues why the problem is hard over $\mathbb{F}_2$ (that is, $P \ne NP$)? What is known about decidability and complexity for other rings? In particular, what is known about complexity over $\mathbb{F}_p$ for p prime > 2?

• The system of polynomial equations defines an algebraic scheme. Is it possible to find algebro-geometric conditions on this scheme, s.t. something can be told about the complexity of SAT restricted to such schemes?

• The solutions of our system of polynomial equations are the fixed points of the Frobenius endomorphism on the corresponding variety over $\bar{\mathbb{F}}_2$. There is a variant of Lefschetz's fixed-point theorem which relates the existence of such points to $l$-adic cohomology. Can this be used to provide some insight on P vs. NP?

This is an agglomeration of several questions, linked by a single observation: SAT is equivalent to determining the existence of roots for a system of polynomial equations over $\mathbb{F}_2$ (note though that the system is represented in non-trivial manner). The reason it is OK to consider more than one equation is because the conjunction of the conditions $f_i(x_1 ... x_n) = 0$ is equivalent to the single condition $\prod_i (f_i(x_1 ... x_n) + 1) + 1 = 0$.

• This reminds of the solution of Hilbert's 10th problem, namely that it is undecidable whether a system of polynomial equations over $\mathbb{Z}$ has roots. Is there a formal relation? Can we use the undecidability over $\mathbb{Z}$ to provide clues why the problem is hard over $\mathbb{F}_2$ (that is, $P \ne NP$)? What is known about decidability and complexity for other rings? In particular, what is known about complexity over $\mathbb{F}_p$ for p prime > 2?

• The system of polynomial equations defines an algebraic scheme. Is it possible to find algebro-geometric conditions on this scheme, s.t. something can be told about the complexity of SAT restricted to such schemes?

• The solutions of our system of polynomial equations are the fixed points of the Frobenius endomorphism on the corresponding variety over $\bar{\mathbb{F}}_2$. There is a variant of Lefschetz's fixed-point theorem which relates the existence of such points to $l$-adic cohomology. Can this be used to provide some insight on P vs. NP?

EDIT: There is an especially appealing encoding of 3-SAT by algebraic varieties. Namely, write an equation of the form $(x + a)(y + b)(z + c) = 0$ for each clause, where $x, y, z$ are variables and $a, b, c \in \mathbb{F}_2$. This seems to yield a non-trivial variety in a natural way, so there's hope non-trivial insight can be obtained from applying algebro-geometric methods.