Summary
This work deals with two complex problems about polynomials: knowing when a set of polynomial equations almost has a solution, and when a polynomial fits nicely inside a collection generated by other polynomials. The authors show that both problems can be solved within a complexity class called the Counting Hierarchy, which is known for capturing certain types of efficient computations. They do this by connecting geometric properties of polynomial maps with algebraic tests called resultants, making it easier to decide these questions. Their findings bring better understanding of the computational difficulty of approximate polynomial problems and related algebraic concepts.
What this means in practice
- •For complexity theory teams: Determine the complexity class for approximate polynomial satisfiability problems to guide algorithm design.
- •For computer algebra system developers: Implement integral closure membership tests using complexity bounds derived from polynomial resultants.
A theory result. No direct application yet.
Authors
Sanyam Agarwal, Archit Hari, Anurag Pandey, Himanshu Shukla
Abstract
Andrews, Garg, and Schost recently, in a breakthrough result, placed Hilbert's Nullstellensatz (HN) in the Counting Hierarchy ($\CH$) using constant-depth circuits for multivariate resultants. While HN deals with exact polynomial satisfiability, Guo, Saxena, and Sinhababu (CCC~2018; Theory of Computing~2019) introduced approximate polynomial satisfiability (APS) as a natural approximative analogue of polynomial system satisfiability. They proved its $\mathsf{NP}$-hardness and a $\PSPACE$ upper bound, and used APS to construct hitting sets for $\overline{\mathsf{VP}}$ in polynomial space, substantially narrowing the GCT chasm in geometric complexity theory. We place APS in the Counting Hierarchy for rational polynomials given by arithmetic circuits. Our proof combines Noether normalization with a geometric restriction on how points in the image of a polynomial map approach the origin, reducing APS to a test on multivariate resultants which allows solvability in $\CH$. It complements the independent and concurrent proofs of Balaji, Shirmohammadi, Tavenas, and Worrell, and Andrews, Garg, Oliveira, and Schost. Moreover, we also place integral closure membership testing in the Counting Hierarchy. Here, the question is whether a given polynomial $f$ is integral over $\C[f_1,\ldots,f_m]$. Our approach uses a global annihilator criterion and an effective degree bound to reduce non-integrality to APS in polynomial time.