PaperlayerView exact revision on arXiv

Source-linked AI summary

Approximate Polynomial Satisfiability is in the Counting Hierarchy

Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell

arXiv:2610.00644v1cs.CC

TL;DR

APS asks whether zero lies in the closure of a polynomial map’s image, a relaxation of exact polynomial feasibility. The paper reduces APS to a resultant-valuation decision problem and proves APS lies in CH over the rationals and finite fields.

  • Problem

    APS asks whether zero lies in the closure of a polynomial map’s image, relaxing the requirement that the input polynomials have a common zero.

    Source: §1 · p. 2, §2 · p. 5

  • Method

    A randomized polynomial-time reduction sends APS to the multivariate resultant valuation problem, whose coefficient tests and fixed quantifier alternation place it in CH.

    Source: §1 · p. 2, §2 · p. 13

  • Results

    APSk lies in the Counting Hierarchy when k is the rationals or a finite field.

    Source: §2 · p. 6

  • Takeaways & Limitations

    A reduction from HNk establishes that APS is NPk-hard.

    Source: §1 · p. 3

    The input conventions assume nonconstant polynomials, with zero polynomials deleted and nonzero constants making an instance negative; finite-field sampling may use an extension of polynomial degree.

    Source: §3 · p. 13, §4 · p. 22

Abstract

from arXiv · show

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.

CNRS, IRIF, France

The authors disclose that AI discussions informed parts of their reductions, while emphasizing that they independently checked and rewrote the mathematical arguments and take responsibility for the paper.

CNRS, IRIF, France

  • AI discussions suggested the HN-to-APS reduction and a univariate substitution, and simplified the original APS-to-MRV reduction.The authors state that they independently checked, developed, and rewrote all mathematical arguments arising from these interactions.Source: CNRS, IRIF, France · p. 1
  • The authors state that they take full responsibility for the paper’s contents and correctness.They also say they independently checked, developed, and rewrote the mathematical arguments arising from the AI discussions.Source: CNRS, IRIF, France · p. 1
  • The AI discussions were limited to suggesting aspects of the reductions rather than supplying unchecked mathematical arguments.The authors report that they independently checked, developed, and rewrote the arguments.Source: CNRS, IRIF, France · p. 1

1 Introduction

The introduction frames APS as a closure-based analogue of polynomial feasibility and places it among applications in approximative complexity. It presents a route from APS to the Counting Hierarchy and discusses consequences for hitting-set certification and null-cone membership.

1 Introduction

  • The paper places APS at the intersection of exact polynomial feasibility and closure questions central to border complexity, including border rank and orbit closures.The introduction also relates polynomial-system solvability to tensor rank and algebraic-circuit existence questions.Source: §1 · p. 2
  • A randomized polynomial-time reduction from APS to the multivariate resultant valuation problem, together with a CH decision procedure for that problem, yields APS in CH.The MRV decision procedure builds on the result that HNk lies in CH for the rationals and finite fields [AGS26].Source: §1 · pp. 2–3
  • APS asks whether all annihilating polynomials of the map vanish at the origin, and a reduction from HNk establishes that APS is NPk-hard.The introduction relates this question to algebraic dependence, which asks whether any nonzero annihilating polynomial exists.Source: §1 · p. 3

1.1 Applications of APS

  • For ordinary VP, failure of a candidate hitting set can be encoded as a Hilbert Nullstellensatz instance, bringing certification into CH using HNk ∈ CH [AGS26].The introduction notes that arbitrary scalar labels prevent simply enumerating all small circuits.Source: §1.1 · pp. 3–4
  • For border VP, a hitting set for approximating polynomials need not remain a hitting set for their limits, motivating separate certification bounds for the border class.Prior work gave PSPACE bounds, and the introduction notes the question of improving them to PH.Source: §1.1 · p. 4
  • The CH result further narrows the GCT chasm associated with constructing normalizing maps by improving the complexity bound for certifying hitting sets.The introduction says earlier PSPACE bounds had already narrowed that gap.Source: §1.1 · p. 4
  • The null cone is also a structured polynomial-feasibility problem whose defining invariant equations are implicit in the group action.It is the common zero set of all positive-degree homogeneous G-invariant polynomials.Source: §1.1 · p. 4
  • Null-cone membership is an image-closure question for the orbit map, so APS gives a PSPACE upper bound for this problem.Over C, the null-cone condition also has the complementary formulation cap(v) = 0.Source: §1.1 · pp. 4–5

2 Main Results and Proof Overview

For rational and finite fields, the section presents a reduction of APS to multivariate resultant valuation (MRV), using a resultant-based polynomial and a valuation test. It then places MRV in the Counting Hierarchy by expressing its defining inequality through resultant-coefficient tests.

Statement of Main Results

  • APSk over Q and finite fields lies in CH via randomized polynomial-time reductions to MRV, over a polynomial-degree finite extension when needed, which lies in CH using [AGS26].For APSQ the reduction targets MRVQ; over finite fields it targets MRVℓ for a finite extension ℓ/k.Source: §2 · pp. 6–7

Algebraic Independence of Input Polynomials

  • A randomized polynomial-time reduction converts general APS instances to minimally dependent ones, preserving APS status and using polynomial-degree finite extensions over finite fields.It adjoins Y, YX1, …, YXs before a generic projection, whose Jacobian has a nonzero minor in every characteristic.Source: §2 · p. 7
  • For a minimally dependent map of n+1 polynomials in n variables, the image closure is defined by an irreducible annihilator H, and APS positivity is equivalent to H(0) = 0.Every proper subset of the coordinate polynomials is algebraically independent.Source: §2 · pp. 7–8

Prescribing the Algebraic Curve

  • For generic a, the prescribed system fi = aiε has a finite nonempty solution set, and positivity holds exactly when some solution gives fn+1 positive valuation.A controlled-degree polynomial Qbad characterizes exceptional choices; sampling from S has failure probability at most (∆bad − 1)/|S|.Source: §2 · p. 8

Proof Outline of Proposition 4

  • When H(0) = 0, specializing its least-degree homogeneous component yields a positive-valuation root, and localization plus an integral extension lifts that root to a solution of the prescribed system.The argument applies in positive characteristic; for generic a, roots of H(a1ε, …, anε, Z) are exactly the fn+1-images of solutions.Source: §2 · pp. 9–10

Multivariate Resultants and fn+1-Images

  • Because the prescribed system may have exponentially many solutions, the proof constructs a polynomial for a succinct representation of fn+1-values across that solution set.Source: §2 · p. 10

Proof Overview

  • Perturbing the homogenized system and taking iterated trailing coefficients yields a polynomial whose factors include affine solution values while factors from infinity are Z-independent [AGS26].The construction addresses the possibility that points at infinity make the unperturbed resultant vanish identically.Source: §2 · p. 11
  • R has a root of positive valuation exactly when its Gauss valuation is strictly less than the valuation of its constant term.This criterion converts the root question into a comparison of two valuations.Source: §2 · p. 12
  • Lemma 12 uses exponent am²+bm+j to encode (a,b,j) lexicographically and proves valuation-comparison equivalence; with T=ε^m² and W=ε^m, the equivalent comparison is an MRV query with distinguished monomial Z0, completing Theorem 2’s reduction.Source: §2 · p. 13

The MRV problem in the Counting Hierarchy

  • MRV lies in CH because its strict valuation inequality reduces to a fixed quantifier alternation over resultant-coefficient vanishing tests, which lie in CH by [AGS26, Theorem 6.7].Standard resultant degree bounds give singly exponential bounds on the indices, so they have polynomial-length binary encodings.Source: §2 · p. 13

3 Encoding and Sampling Conventions

The section sets input-representation conventions and shows how circuit inputs can be converted to dense polynomial systems without changing APS status. It also specifies the field and sampling representations used in the complexity bounds.

3 Encoding and Sampling Conventions

  • Rational inputs use binary-integer pairs, while Fq inputs use the power basis of Fp[U]/(µ(U)); polynomial encodings and input lengths follow the stated sparse and bit-length conventions.Over Q, clearing denominators preserves APS status; identically zero polynomials may be deleted, while a nonzero constant makes the instance negative.Source: §3 · pp. 13–14
  • Circuit-, sparse-, and dense-encoded APS instances are polynomial-time equivalent, including a polynomial-time reduction from division-free circuits to dense encoding.The reduction introduces gate variables and auxiliary variables to encode approximate satisfaction using a system of low-degree polynomials.Source: §3 · pp. 14–15
  • For circuit inputs, gate equations preserve approximate satisfiability in both directions: circuit approximate zeros extend to the constructed system, and its approximate zeros yield circuit approximate zeros.The construction uses one variable per gate and h = ⌈log2(L + 1)⌉ auxiliary variables per input variable; its polynomials have degree at most 3.Source: §3 · pp. 14–15
  • Random choices avoid nonzero polynomials of degree at most 2^poly(N) by sampling from a sufficiently large set, using rational grids over Q or polynomial-degree finite-field extensions when needed.Sampling and extension construction can be bounded in running time with arbitrarily small failure probability.Source: §3 · pp. 15–16

4 Reducing APS to MRV

This section develops randomized polynomial-time reductions from APS to MRV, over the rationals directly and over finite fields via a polynomial-degree extension, using minimally dependent instances. It establishes correctness for positive and negative instances and characterizes positive minimally dependent cases through generic finite fibers and valuation tests.

4 Reducing APS to MRV

  • A randomized polynomial-time reduction maps general APS instances to minimally dependent instances while preserving APS status.Over Q, output coefficients remain rational; over finite fields, they may lie in an extension of polynomial degree.Source: §4 · p. 16
  • For minimally dependent inputs, outside the zero set of a nonzero polynomial, the first n equations have a finite nonempty solution set, and positivity is equivalent to a last-coordinate value of positive valuation.The proposition allows a suitable permutation of the input coordinates.Source: §4 · p. 17
  • A minimally dependent tuple has an irreducible relation H whose vanishing at the origin is equivalent to the tuple being a positive APS instance.The relation generates the kernel of the map from the polynomial ring in n+1 output variables to the input polynomial ring.Source: §4 · p. 18
  • When the generic fiber V is finite and nonempty, the trailing resultant R0 is nonzero and factors into linear forms associated with projective limit points.For affine limit points, the factor’s trailing coefficient in W is Z − fn+1(x).Source: §4 · pp. 20–21
  • A randomized polynomial-time Turing reduction maps APS over Q to MRV over Q, and APS over a finite field to MRV over a polynomial-degree finite extension.The reduction makes n + 1 oracle queries and has total error strictly less than 1/3.Source: §4 · pp. 22, 24
  • The reduction tries each of n + 1 possible distinguished coordinates, samples parameters, and encodes a resultant test as an MRV query using substitutions for T and W.It does not compute the resultant explicitly; the substituted homogeneous forms have polynomial-size sparse descriptions.Source: §4 · pp. 22–24
  • For positive APS instances, the appropriate coordinate choice yields an accepting MRV query except with small error, by sampling parameters and applying Schwartz–Zippel.For the good coordinate choice, the query accepts when the finite nonempty solution set contains a point whose remaining coordinate has positive valuation.Source: §4 · p. 23
  • Assuming Qj(a) ≠ 0 for every coordinate choice j, each corresponding MRVℓ query returns no: a yes answer would yield an approximate solution, contradicting that f is a negative APS instance.Combining the preceding bound with Proposition 3’s error probability and, over finite fields, errors from bounded-time construction and extension-field sampling gives total error strictly less than 1/3 after choosing constants appropriately.Source: §4 · p. 24

5 MRV is in the Counting Hierarchy

The section establishes that the multivariate resultant valuation problem is in the Counting Hierarchy over the rationals and finite fields. It reduces the valuation test to coefficient tests and polynomial-length quantified indices.

5 MRV is in the Counting Hierarchy

  • The relevant resultant coefficient problem is in CH for sparse homogeneous input forms with a binary-encoded exponent tuple.Over Q, clearing denominators scales all resultant coefficients by the same nonzero integer; over finite fields, the cited resultant result applies over Fq[Y].Source: §5 · pp. 24–25
  • Sparse MRV inputs can be handled by the dense-coefficient resultant circuits because each indexed coefficient can be recovered in polynomial time from the sparse description.The stated degree and height bounds keep output coefficient representations to at most 2^poly(N) bits.Source: §5 · p. 25
  • MRVk is in CH for k = Q or a finite field.The proof applies the CH result for bits of the multivariate resultant to the coefficient tests defining MRV.Source: §5 · pp. 24–25
  • The strict MRV inequality is expressed using polynomial-length existential and universal coefficient-index tests, whose fixed alternation remains in CH.A coefficient is zero exactly when all its indexed bits are zero, and the resultant circuit's coefficient bits have polynomial-length addresses.Source: §5 · p. 25

6 Relating APS to HN and ETR

This section gives polynomial-time reductions from Hilbert’s Nullstellensatz to APS and, over the rationals, from APS to ETR. It establishes the reductions through an equivalence-preserving construction and an existential real formula.

6 Relating APS to HN and ETR

  • The section gives a polynomial-time reduction from Hilbert’s Nullstellensatz to APS in any characteristic, and reduces APS_Q to ETR.The stated Nullstellensatz reduction applies in any characteristic; Theorem 16 states the APS-to-ETR reduction for APS_Q.Source: §6 · pp. 25, 27
  • For an HN instance p, the constructed map satisfies 0 ∈ p(K^n) iff 0 ∈ f(K^n), and the reduction runs in polynomial time.The proof constructs components from the input polynomials and uses an effective Nullstellensatz degree bound to keep the additional polynomials outputtable in polynomial time.Source: §6 · pp. 25–26
  • For rational APS, the ETR reduction represents the complex polynomial map using real and imaginary parts and encodes the predicate α = 0 existentially.The proof relates α to the distance from a semialgebraic set to 0, then uses a polynomial-length existential formula.Source: §6 · p. 27
  • A rational APS instance is positive exactly when the resulting existential sentence of ETR is true.The proof states both equivalences: positivity of APS_Q iff α = 0, and α = 0 iff the ETR formula is true.Source: §6 · p. 27
Loading 2610.00644v1…