Interesting Math

Polynomials and Complexity

Polynomials make up a fundamental building block of mathematics. Their study has produced a rich theory through the years, with much written about when they have integer solutions, when they have solutions by radicals, and entire branches of mathematics built on top of the geometry of their zero sets. One celebrated theorem in this area is David Hilbert's Nullstellensatz (German for zero set theorem). In a weak form, suppose we have a field F and a set of polynomials f_i in several variables over this field. Hilbert then tells us that these polynomials do not have a common zero if and only if there exist polynomials g_i such that

The proof is somewhat involved and not our topic today. If you are interested in it there are many expositions to be found, and it forms a fundamental tool in algebraic geometry. There is a problem with the Nullstellensatz though. It is non-constructive, it does not tell us how to find those g_i in an algorithmic fashion, and it is non-obvious from the statement or proof that this should be possible to compute at all. Our skepticism about whether or not it is possible to compute the solution comes from the negative answer to Hilbert's tenth problem: there is no algorithm to decide whether or not a polynomial with integer coefficients has an integer solution. This result, the combined work of Davis, Matiyasevich, Putnam, and Robinson, suggests that lurking in polynomials is a mess of computational complexity.

The Nullstellensatz is more tractable than Hilbert's tenth problem, it has been shown that there is a procedure to decide if a set of polynomials has a common zero, however the best known algorithms take exponentially many steps. In computer science, the decidability of a computational problem is usually not very interesting. We also require efficiency, solving a problem in a feasible amount of time. It is generally agreed that algorithms that take an amount of time polynomial in their input size are efficient, ones that we can actually implement on a computer. In the case of our Nullstellensatz program the input size would be the number of terms times how many bits it takes to represent a term (the degree of each variable, and the coefficient). The careful reader (or seasoned computer scientist) will object that we cannot represent all complex numbers in bits. To avoid this difficulty we will restrict our attention to Z/2Z, the finite field of order two, and its algebraic closure (every time a polynomial does not have a root, add a new number, like i in the case of the real numbers and x²+1). So, we ask is there a polynomial time algorithm to decide if a set of polynomials over Z/2Z has a common zero.

The answer is an open question, and you might have heard of it. Such an algorithm exists if and only if P=NP. For those not in the know, P?=NP is one of the central questions in complexity theory. Informally it asks if an easily verified problem is also easily to solve. Formally, P is the set of computational yes/no questions that can be answered in an amount of time polynomial in the input size. NP is the set of computational yes/no questions that we can, when given a solution to the problem, check the solution in time polynomial in the input size. The set NP has been characterized by so-called NP-complete problems; an NP-complete problem has the property that any other problem in NP can be converted to it in polynomial time. Steve Cook showed that the problem of deciding if a boolean formula is satisfiable is NP-complete. If we note that in Z/2Z multiplication behaves like 'and' and addition like 'xor', it becomes clear that if we can find common zeroes in sets of Z/2Z polynomials we can find solutions of boolean formulas, so our Nullstellensatz is at least as hard as an NP-complete problem. Evaluating a polynomial in Z/2Z can be done efficiently (the maximum number of multiplications per term times the number of terms is polynomial in the degree and the number of terms). Hence deciding the Nullstellensatz is NP-complete.

The past century of mathematics has been filled with many fascinating existence results; many are proven in a non-constructive fashion. With the rise of computer science, the computability (is there an algorithm to find solutions) and complexity (is such an algorithm efficient) of mathematical structures is now being considered. The Nullstellensatz is one such area, and this discussion was inspired by Steve Smale's article "Mathematical problems for the next century" which presents computational considerations as one of the likely driving themes in the next century of mathematics. Topology is also being enlivened with algorithmic considerations. Poincare's conjecture (recently proven) can be stated informally as "if it looks like a sphere it is a sphere", but the complexity of figuring out whether or not something looks like a 3-sphere is NP-hard (you can reduce other problems in NP to it) but it is not known if it lies in NP or not.

Problem of the Issue: (from Mathematics Made Difficult by Linderholm) A farmer acquires an algebraically closed field by extending his field finitely. What can be said about the original field?

Edgar A. Bering IV
ebering@uwaterloo.ca