Suppose we are given a system of polynomial equations in \(n\) variables, where each polynomial has degree at most \(d\), and the coefficients are integers given as binary. We want to determine whether this system of equations has any solutions over the complex numbers. In other words, we want to determine whether the algebraic set specified by the system of polynomial equations is nonempty.
What computational complexity class class does this problem fall into? Can we do it in polynomial time if we take the degree \(d\) to be a fixed constant?
As it turns out, this problem is NP-hard, even for \(d = 2\). The proof is straightforward and requires no algebraic geometry or other “hard” math—you just have to know the trick.
We can reduce from the 0-1 integer linear programming problem, which is one of Karp’s original 21 NP-complete problems. 0-1 integer programming is defined as follows:
Input: \(m\)-by-\(n\) integer matrix \(A\) and length-\(m\) integer vector \(b\)
Output: true if and only if there exists a length-\(n\) 0-1 vector \(x\) such that \(Ax = b\)
We can write the matrix equation \(Ax = b\) as a set of \(m\) linear equations in \(n\) variables. This gives us a system of polynomial equations, but without further constraints we are not guaranteed to end up with a solution that is valid for the original 0-1 integer programming problem, since the variables are allowed to range over \(\mathbb{C}\) rather than being restricted to 0 or 1.
However, this is easy to fix—we just need to add additional polynomial equations that constrain each variable to be either 0 or 1. It is sufficient to add an equation \({x_i}^2 - x_i = 0\) for each variable \(x_i\), since the solution set of this equation is exactly \(x_i \in \{0, 1\}\). This gives us a system of \(m + n\) polynomial equations in \(n\) variables with maximum degree 2, where an assignment of the variables is a solution of the system if and only if it is a solution to the original integer programming problem. Since this reduction is clearly possible to perform in polynomial time, we can conclude that determining whether a system of degree-2 polynomials with integer coefficients has a solution is NP-hard.
