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

Markus Bläser, Sagnik Dutta, Gorav Jindal · 2025

Read Problems from Optimization and Computational Algebra Equivalent to Hilbert’s Nullstellensatz by Markus Bläser, Sagnik Dutta, Gorav Jindal (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2510-19704.txt.

Introduction

Markus Bläser, Sagnik Dutta, and Gorav Jindal pin down the exact difficulty of several problems in optimization and computational algebra by tying them to Hilbert's Nullstellensatz problem. That problem asks whether a system of polynomial equations has a common solution, and many efficient algorithms secretly rest on it. The authors treat it as a complexity class and test familiar problems against it.

Transforming one polynomial into another by an affine change of variables turns out to be at least as hard as the Nullstellensatz problem over any field. For real polynomials, deciding stability, convexity, and hyperbolicity are all complete for the universal theory of the reals. The results tell algorithm designers exactly how hard these problems are, guiding where to look for efficient methods.

Catalog record

CREATORMarkus Bläser, Sagnik Dutta, Gorav Jindal
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE91 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2510-19704

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Problems from Optimization and Computational Algebra Equivalent to Hilbert’s Nullstellensatz Markus Bläser, Sagnik Dutta, Gorav Jindal Abstract Solving polynomial systems is a powerful tool in optimization and computational algebra. The most efficient algorithms for many problems from optimization or algebra often stem from formulating these problems as a system of polynomial equations. This is due to the fact that there are astonishing algorithms for deciding feasibility of polynomial systems, like Koiran’s 𝖠𝖬 \mathsf{AM} -algorithm over the complex numbers (assuming GRH) or Renegar’s 𝖯𝖲𝖯𝖠𝖢𝖤 \mathsf{PSPACE} -algorithm over the reals. To formalize this, Blum, Shub, and Smale [ 2 ] introduced Hilbert’s Nullstellensatz Problem: Hilbert’s Nullstellensatz Problem 𝖧𝖭 R \mathsf{HN}_{R} over some ring R R asks whether a given set of multivariate polynomials over R R has a common solution in R R . 𝖧𝖭 𝔽 2 \mathsf{HN}_{\mathbb{F}_{2}} defines the class 𝖭𝖯 \mathsf{NP} , since every Boolean formula can be arithmetized appropriately. Over the real numbers, 𝖧𝖭 ℝ \mathsf{HN}_{\mathbb{R}} is equivalent to the existential theory of the reals ∃ ℝ \exists\mathbb{R} , which is astonishing, since in ∃ ℝ \exists\mathbb{R} , we can define semi-algebraic sets. We can view 𝖧𝖭 R \mathsf{HN}_{R} as a parameterized complexity class: for every ring R R , we get a class by taking the downward closure of 𝖧𝖭 R \mathsf{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 a system of polynomials equations is optimal, since we can reduce Hilbert’s Nullstellensatz to them. We first show that two well-known problems from algebra are equivalent to or at least as hard as Hilbert’s Nullstellensatz over fields. The first one is the Affine Polynomial Projection Problem, which given two polynomials, asks whether one of them can be transformed into the other by an affine linear projection of the variables. Kayal [ 15 ] proves that this problem is 𝖭𝖯 \mathsf{NP} -hard. Here we improve this lower bound by showing that it is harder than 𝖧𝖭 F \mathsf{HN}_{F} for any field F F . As a corollary, we obtain that this problem is complete for the existential theory of the reals, which answers an open question asked in [ 30 , A14, open question] . 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 R that are not fields, Chillara, Grichener, and Shpilka [ 7 ] showed that this problem is hard for 𝖧𝖭 R \mathsf{HN}_{R} . They left it as an open problem whether this is also true for fields. We here resolve this question in the positive. Over infinite fields F F , where 𝖧𝖭 F \mathsf{HN}_{F} is complete for 𝖭𝖯 F \mathsf{NP}_{F} (in the BSS model), we show that the Sparse Shift Problem is even equivalent to 𝖧𝖭 F \mathsf{HN}_{F} . Second, we turn to an important case of Hilbert’s Nullstellensatz over the real numbers. Real-stable polynomials have been a successful tool in mathematics and computer science in the recent years. For instance, the solution to the Kadison-Singer problem by Marcus, Spielman, and Srivastava [ 21 ] is deeply connected to real stable polynomials, and so is the improvement of the approximation performance of metric TSP by Karlin, Klein, and Oveis Gharan [ 14 ] , just to give two examples. We here prove that testing whether a given polynomial is real stable is equivalent to the complement of 𝖧𝖭 ℝ \mathsf{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. 1 Introduction Solving systems of polynomial equations is a central technique in both optimization and computational algebra, serving as a unifying framework for a wide range of algorithmic problems. Many of the most efficient algorithms in these domains are built upon the insight that complex problems—ranging from feasibility in nonlinear programming to questions in algebraic geometry—can be reduced to the task of solving a polynomial system. This approach is powerful because it takes advantage of the existence of surprisingly efficient algorithms for deciding the solvability of polynomial systems. Over the complex numbers, Koiran [ 17 ] demonstrated that the feasibility of polynomial systems lies in the class \mathsf{AM} (Arthur-Merlin games), assuming the Generalized Riemann Hypothesis (GRH). This result (conditionally) places the problem in a probabilistic class that is believed to be much smaller than \mathsf{PSPACE} . Canny [ 6 ] and Renegar [ 26 ] developed \mathsf{PSPACE} -algorithms for deciding the feasibility over real numbers. These results highlight that, despite the apparent algebraic and geometric complexity of polynomial systems, their computational complexity can be surprisingly low. As a result, formulating problems as polynomial systems not only provides a unifying language, but also yields algorithms whose complexity is as low as possible. Note that in this context, even an upper bound like \mathsf{PSPACE} is surprisingly low, since real numbers are infinite objects and until the work of Tarski [ 36 ] , it was not even clear whether this problem was decidable at all. To formalize this, Blum, Shub, and Smale, see [ 2 ] , introduced Hilbert’s Nullstellensatz Problem: For an arbitrary ring R , the problem is defined as follows: \mathsf{HN}_{R} (Hilbert’s Nullstellensatz over ring R ) : Given a set of polynomial equations f_{1}=0,\cdots,f_{t}=0 where each f_{i} is from R[x_{1},\cdots,x_{n}] , decide if there exists a vector (a_{1},\cdots,a_{n})\in R^{n} such that f_{i}(a_{1},\cdots,a_{n})=0 for all i\in[t] . This problem is also called the Polynomial Feasibility Problem, but in the present paper, we will use the term Hilbert’s Nullstellensatz as coined by Blum, Shub and Smale. When R is an arbitrary ring, the coefficients of the input polynomials might not be efficiently representable on a Turing machine. Therefore, it makes more sense to use the Blum-Shub-Smale (BSS) model of computation where the registers can store arbitrary elements of the ring and each ring operation is assumed to cost unit time. However, often it’s possible to consider the problem on the Turing machine model as well. If R is a finite field, then the coefficients of the input polynomials will have constant bit complexity. If R=\mathbb{R} or \mathbb{C} , we can assume the coefficients of the inputs to be integers. For other rings, we can restrict the coefficients to be ring elements with small bit complexity. In such settings, \mathsf{HN}_{\mathbb{F}} is known to be \mathsf{NP} -hard for all fields \mathbb{F} . The problem of \mathsf{HN} over the real field \mathbb{R} is particularly interesting because it is complete for the well-studied complexity class \exists\mathbb{R} . This class captures the complexity of deciding the truth of sentences in the existential theory of the reals (ETR). Formally, the ETR language consists of all true sentences of the form \exists x_{1},\dots,x_{n}\ \phi(x_{1},\dots,x_{n}) , interpreted over the reals, where \phi is a quantifier-free formula written as a Boolean combination of atomic formulas involving the constants 0,1 , variables, the operations +,\cdot , and the comparison operators <,>,\leq,\geq,= . The class \exists\mathbb{R} is the set of all languages that are

Read the complete text