Approximate polynomial satisfiability problem lies in counting hierarchy
Approximate Polynomial Satisfiability is in the Counting Hierarchy
Computational Complexity
Summary
This paper studies a problem called approximate polynomial satisfiability, which asks whether zero is close to the values of certain polynomial functions. This question generalizes checking if polynomial equations have exact solutions, a well-known math challenge. The authors prove that deciding this approximate version is easier than previously thought—it belongs to a complexity class known as the counting hierarchy, rather than requiring more computational power. They also connect this problem to others in algebra and improve how quickly some related problems can be checked.
What this means in practice
- •For complexity theorists: Better understand the complexity bounds of approximate polynomial problems by relating them to counting hierarchy classes.
- •For algebraic algorithm designers: Use improved complexity bounds to design faster algorithms for verifying border rank and null-cone membership problems.
A theory result. No direct application yet.
Authors
Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell
Abstract
The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\boldsymbol f(K^n)}$ for a polynomial map $\boldsymbol f=(f_1,\ldots,f_m)$ with $f_i\in k[X_1,\ldots,X_n]$. APS is a natural topological analogue of Hilbert's Nullstellensatz, namely the question of whether a given system of polynomial equations has a common zero. APS captures several problems in algebraic complexity, including border rank, hitting sets for border classes, and null-cone membership; it is known to be NP-hard and in PSPACE. We show that APS lies in the Counting Hierarchy (CH) over both the rationals and finite fields, substantially improving the known PSPACE upper bound. Our proof builds on a recent breakthrough due to Andrews, Garg, and Schost (FOCS 2026) on deciding Hilbert's Nullstellensatz in CH. As a corollary, our result improves the complexity of certifying hitting sets for border classes from PSPACE to CH. We also give a polynomial-time reduction of Hilbert's Nullstellensatz to APS, valid in any characteristic. In characteristic zero, we give a reduction of APS to the decision problem for the existential theory of real closed fields. Overall, our results place approximate polynomial satisfiability closer in complexity to exact polynomial feasibility and as a byproduct give improved complexity bounds for several problems arising in approximative complexity.