### Better Know a Theorem: Solvability of Polynomial Equations

26Apr07

Let’s say I hand you a bunch of polynomial equations/inequalities and some variables, e.g.,

{x > 0, y < x, x2-y3+z=0, z4+4z>16} in variables x, y, z.

Either there exists a triple of values for which all the equations and inequalities are satisfied, or there doesn’t. How can you tell? Is there an efficient procedure to figure this out? It depends on the types of variables and equations. Here are a few representative cases.

• Real variables with linear (in)equalities: Computable in polynomial time.
(A linear equation is, roughly, one where you aren’t allowed to multiply (or power) variables. I.e., x+3y-5z = 0 is linear but xy = 1, x2 + y2 = 1 are not.) This result is a cornerstone of the theory of linear programming, and was proved first by Khachiyan in 1972. Linear programming is also efficient in practice.
• Integer variables with linear (in)equalities: Computable and NP-complete.
Essentially, what I mean is that a computer program can solve these problems, however we don’t know any fast ways of doing it. It’s NP-completeness suggests that no fast way exists. The NP-completeness was first proved by Karp (also in 1972), even if the variables only take on the values 0 and 1. For relatively small problems, mixed integer programming is an efficient practical solution.
• Real or complex variables with polynomial (in)equalities: Computable and NP-hard.
Reals: proved first by Tarksi in the 1930s; Cylindrical Algebraic Decomposition is more practical. In fact these methods even work with logical quantifiers and boolean operators, e.g., “there exists x such that x>z and for all y, either …”
Complex: here there are no inequalities, just equalities. Groebner bases are the tool to use and were invented in the mid-1960s.
The NP-hardness follows from Karp’s result by adding the constraint x2=x to every variable. However, I think that the best algorithms known are not in NP, rather they are doubly exponential.
• Integer/whole number variables with polynomial (in)equalities: Not computable.
Also known as Hilbert’s 10th problem or solvability of diophantine equations. The proof was completed in 1970 by Matiyasevich. What “not computable” means is that he proved no computer program (even a quantum one) could solve all diophantine equations. This result itself relies on Turing’s halting problem, and I think it’s quite pretty (so much that I gave a talk on it once).

That’s it for now, go solve some things!