More problems that seem easy but are actually NP-hard

In the last post, I illustrated how the 0-1 integer linear programming problem can be reduced to solving a multivariate system of linear and quadratic polynomials over the complex numbers, demonstrating that the latter problem is NP-hard. Let’s see what other problems we can prove are NP-hard by reduction from 0-1 integer programming.

Continue reading More problems that seem easy but are actually NP-hard

How hard is determining whether an algebraic set is nonempty?

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.

Continue reading How hard is determining whether an algebraic set is nonempty?