Problems from Optimization and Computational Algebra Equivalent to Hilbert’s Nullstellensatz

Solving polynomial systems is a powerful tool for designing algorithms in optimization and computational algebra. Formally, this problem is called Hilbert’s Nullstellensatz problem \(\textsf{HN}_R\): given multivariate polynomials over some ring \(R\), it asks whether they have a common solution in \(R\). For every ring \(R\), we can also view \(\textsf{HN}_R\) as a parameterized complexity class by taking the downward closure of \(\textsf{HN}_R\) under polynomial-time many-one reductions. In this work, we show that for many important problems from optimization and algebra, formulating them as systems of polynomial equations is optimal, since we can reduce Hilbert’s Nullstellensatz to them. We first consider the Affine Polynomial Projection Problem, which, given two polynomials, asks whether one of them can be transformed into the other by an affine projection of the variables. Kayal (STOC 2012) proved that this problem is \(\textsf{NP}\)-hard. Here, we improve this lower bound by showing that it is as hard as \(\textsf{HN}_F\) for any field \(F\). The second problem is the Sparse Shift Problem, which asks whether for a given polynomial, there is an affine shift that reduces the number of monomials. For integral domains \(R\) that are not fields, Chillara, Grichener, and Shpilka (STACS 2023) showed that this problem is \(\textsf{HN}_R\)-hard. We extend their result to fields: over infinite fields \(F\), where \(\textsf{HN}_F\) is complete for \(\textsf{NP}_F\) (in the BSS model), we show that the Sparse Shift Problem is equivalent to \(\textsf{HN}_F\). Next, we turn to the important case of Hilbert’s Nullstellensatz over the real numbers. Real-stable polynomials have been a successful tool in mathematics and computer science in recent years, from solving the Kadison-Singer problem to improving the approximation performance of the metric TSP. We prove that testing whether a given polynomial is real stable is equivalent to the complement of \(\textsf{HN}_{\mathbb{R}}\), or equivalently, to the universal theory of the reals \(\forall\mathbb{R}\). We show that the same is true for testing convexity and testing hyperbolicity, as well as for testing whether a biquadratic form is nonnegative, completely settling the complexity of all of these problems.