# SAT and Arithmetic Geometry

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?

-
decidability over finite fields is trivial, as there are only finitely many choices! – Dima Pasechnik Dec 6 '12 at 14:23
@Dima Pasechnik : This is obvious. I asked about complexity over finite fields and decidability for other (infinite) rings – Squark Dec 6 '12 at 15:00

I'm hoping a real expert comes by to give a better answer, but these are things I've thought about a bit. Here are some thoughts:

(1) You should separate notions of computability (is there an algorithm?) and complexity (will the algorithm terminate in my lifetime?) Hilbert's 10th problem is a question about computability. Questions about SAT, solving equations over finite fields, or basically any computation in algebraic geometry over an algebraically closed field, such as computing betti numbers and Frobenius eigenvalues1, are all computable; the question is how complex they are.

(2) Given an instance of SAT, impose not only the various binary equations you are thinking of, but also the equations $x_i^2=x_i$ for all $i$. Now all of the solutions over $\mathbb{F}^{alg}_2$ live in $\mathbb{F}_2$. So, expanding the size of your problem linearly, you can make there be no difference between working in the boolean field and in its algebraic closure.

This transformation suggests that sophisticated notions like cohomology and Frobenius action will not be useful for the general question of counting solutions to equations over $\mathbb{F}_2$. If your family of equations over $\mathbb{F}_2$ contains the relations $x_i^2 = x_i$ then the solutions are just finitely many points all defined over the ground field, so all cohomology is trivial other than $H^0$ and the Frob action is trivial. So, for at least some equations over $\mathbb{F}_2$, the geometry doesn't give you any tools other than going back to solving the SAT problem.

I would very much like to see someone define and study the notion of which problems are "ALGEBRAIC GEOMETRY-HARD". Ravi's work on Murphy's law (and the people who have followed him) have this flavor, but they don't actually talk about computational complexity.

(4) Your motivation may be in the opposite direction. That is to say, you may be hoping to start with a SAT problem and create equations over $\mathbb{F}_2$ for which the high power tools do help you. I can't prove this is impossible, but I'm skeptical.

That said, there is some work which points against my skepticism. Jesus De Loera and his collaborators (start here and, if you are interested, continue by reading all the papers on algebraic optimization here) have been taking standard hard instances of NP-complete graph theory problems, encoding them as algebraic geometry problems and beating pure graph theoretic algorithms. The results are entirely experimental, but the experimental data makes this method look surprisingly good.

Harm Derksen has tried a similar approach for Graph Isomorphism. He can prove that his methods at worst only polynomially worse than the classic Weisfeiler-Lehman algorithm and, for the Cai-Furer-Immerman graphs, his methods are exponentially better.

One interesting feature of these papers is that they discard Groebner basis methods in favor of brute force. For example, to test whether $g_1$, $g_2$, ..., $g_n$ generate the unit ideal, rather than using Groebner bases, De Loera et al simply guess an upper bound for the degree of polynomials $f_i$ obeying $\sum f_i g_i =1$ and solve this as a family of linear equations in the coefficients of the $f_i$.

(5) There is a general principle, whose precise statement I don't know, that the difficulty of computing with a projective variety $X$ is controlled by its Castelnuovo-Mumford regularity. Googling on "Castelnuovo Mumford regularity complexity" turns up lots of references where one could start digging, though I didn't find a statement simple enough to quote.

My understanding (but I am not an expert) is that varieties created by encoding combinatorial problems in algebraic geometry tend to have very high CM regularity.

1 Frobenius eigenvalues can be described as the eigenvalues of geometric Frob acting on a variety over $\mathbb{F}^{alg}_p$, so you can define them without talking about varieties over nonaglebraically closed fields, although you'll certainly miss some of the motivation.

-
Vakil's work actually uses Mnev's Universality Theorem, which in a way has a computational flavour. – Dima Pasechnik Dec 6 '12 at 17:32
Thanks a lot for your answer! I want to point out that I realize very well the distinction between decidability and computability. However, my naive intuition tells me that a problem which is close to an undecidable problem must have high complexity. For example the halting problem is undecidable whereas deciding whether a program halts in k steps is EXP-complete. Deciding whether a program halts on every output is even higher in the undecidability hierarchy (I think) whereas deciding whether a program halts on every output in k steps is NEXP-complete – Squark Dec 6 '12 at 17:58
Supporting the skepticism in (4), i once saw a talk by Anders Bjoerner, where he mentioned a "program" to prove P≠NP. He said the first step is to find a good description of a Boolean function as a variety. According to him, this would the most difficult thing to come up with (the rest being \'etale cohomology...) – Camilo Sarmiento Dec 7 '12 at 17:30

Which field you work over is not important for encoding SAT, because as pointed out by David Speyer, you can put in the equation $x^2=x$ to make $x$ take on only the values $0,1$. You can encode $x\wedge y$ by $xy$ and $x\vee y$ by $x+y-xy$. So determining if a system has a solution is at least NP-hard. My understanding from surveying the computer science literature some time back is that over $\mathbb C$, it is known that determining if a system has a solution is in PSPACE unconditionally and is in a complexity class called AM, which is just above NP, if one assumes the generalized Riemann Hypothesis. See Pascal Koiran, Hilbert's Nullstellensatz is in the polynomial hierarchy. J. Complexity 12 (1996), no. 4, 273–286. I don't know if the results have been improved since. This was the most recent I had found.

-
Thank you for your answer! – Squark Dec 6 '12 at 18:03
Silly notational point: If you literally use $x+y-xy$, your formula could get exponentially long. One could solve this by introducing new variables but I think it's more elegant to just write $1-(1-x)(1-y)$. – Will Sawin Dec 7 '12 at 17:40
@Will: If you encode 3SAT instead of SAT, each clause will have a constant-size translation, no matter how complex the translation of $\lor$ is. – Emil Jeřábek Dec 10 '12 at 11:35

As for the first question, solvability of a system of polynomial equations is NP-complete over every finite field, and NP-hard for every integral domain. The reduction was already mentioned in David Speyers’s answer: add $x_i^2-x_i$ to your system for every variable $x_i$.

The exact complexity of solvability over infinite domains is not so easy to answer. To begin with, it may significantly depend on the representation of the polynomial and its coefficients.

• Solvability over $\mathbb Z$ is undecidable ($\Sigma^0_1$-complete). This is the MRDP theorem. The decidability of solvability over $\mathbb Q$ is an open problem.

• Solvability of polynomials with rational coefficients over $\mathbb R$ or $\mathbb C$ is in PSPACE, and it is not known whether one can do better. Assuming the generalized Riemann hypothesis, solvability of rational polynomials over $\mathbb C$ is in AM, and therefore in the second level of the polynomial hierarchy. Note that AM = NP under some plausible assumptions from circuit complexity.

• Solvability over the algebraic closure of a finite field is also decidable, though I do not know offhand what are the complexity bounds (but it should be again something in the vicinity of EXP or PSPACE). The keyword is “effective Nullstellensatz”.

-
It seems you have the same answer as me while I was typing. – Benjamin Steinberg Dec 6 '12 at 16:23
Yes, we were writing up the answers simultaneously. Happens all the time. – Emil Jeřábek Dec 6 '12 at 16:33
Thanks a lot for your answer! – Squark Dec 6 '12 at 18:00

I'm going to address just one aspect of your question, which has been restated in some of the answers and comments, about whether there is any formal connection between undecidability and computational complexity.

This is certainly a very tempting idea, and you could argue that one of the main reasons to conjecture that the polynomial hierarchy does not collapse (this is a standard generalization of the conjecture that P≠NP) is that the infinitary analogue of the polynomial hierarchy, namely the arithmetical hierarchy, is known not to collapse. Of course we know, for example from the Baker–Gill–Solovay theorem, that we can't naively carry over all intuitions from computability theory over to complexity theory, but the analogy remains in the back of the minds of many people working in this subject.

Perhaps closer to your question are two papers by Michael Freedman, Limit, logic, and computation and K-SAT on groups and undecidability. The latter paper in particular notes that 2-SAT is polytime solvable and 3-SAT is NP-complete, and constructs infinitary analogues of these two problems that are respectively decidable and undecidable. Your observation about the analogy between the MRDP theorem and the hardness of solving systems of equations over $\mathbb{F}_2$ could be thought of as being in the same vein. Unfortunately, while intriguing, so far these analogies don't seem to have yielded any significant insights into the P≠NP problem.

-

David mentioned in his answer results where Groebner bases are not used. However, Groebner bases for polynomial systems aren't the best available tools theoretically, either. E.g. the best theoretical results for complexity of solving 0-dimensional systems follow a route of symbolically deforming the system into one for which the Groebner basis is trivial to find, and then using Stickelberger Lemma to find roots of the deformed system, and finally taking the limit. Details of this are described e.g. in this book.

Groebner bases (in characteristic 0) are also usually beaten by the machinery of semidefinite programming relaxations. Perhaps not coincidentally, a lot of recent work in computational complexity (in particular, approximation algorithms) uses semidefinite programming relaxations, too.

There is also a line of research where the complexity is investigated w.r.t. arithmetic operations in $\mathbb{C}$ (or $\mathbb{R}$) having unit cost.

-
Thank you for your answer! – Squark Dec 6 '12 at 18:03

More unexpected to me is the reduction from SAT to linear system over $\mathbb{N}_0$ (including $0$).

Monotone one in three SAT is NP-complete and is a conjunction of clauses, each clause is three boolean variables $(x,y,z)$. To satisfy a clause exactly one variable must be true.

The reduction to linear system over $\mathbb{N}_0$ is for each clause add the linear equation $x + y + z = 1$.

Solving the resulting system over $\mathbb{Z}$ is easy, but over $\mathbb{N}_0$ is NP-complete.

-