### 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, x

^{2}-y^{3}+z=0, z^{4}+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, x*) 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.^{2}+ y^{2}= 1 are not.**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 x^{2}=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!

Advertisements

Filed under: b.k.a.t., complexity | Leave a Comment

## No Responses Yet to “Better Know a Theorem: Solvability of Polynomial Equations”