Metraipolis › archive › dc_8b53b9ea4bc4
Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy — arXiv:2610.42138
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2610.42138
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-02T08:07:39.428Z
- SHA-256 of the archived text
670c415c0a3b2549cb097a49700be19be7bdab7b4778f3d799237ee689608b94- Stable URL of this page
https://metraipolis.com/documento/dc_8b53b9ea4bc4
How to cite
Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy — arXiv:2610.42138 — arXiv (en), https://arxiv.org/abs/2610.42138 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_8b53b9ea4bc4 (Metraipolis archive dc_8b53b9ea4bc4, sha256 670c415c0a3b2549cb097a49700be19be7bdab7b4778f3d799237ee689608b94)
BibTeX
@misc{dc8b53b9ea4bc4,
title = {Approximate Polynomial Satisfiability and Integral Closure Membership in the Counting Hierarchy — arXiv:2610.42138},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2610.42138},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_8b53b9ea4bc4; sha256 670c415c0a3b2549cb097a49700be19be7bdab7b4778f3d799237ee689608b94},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.42138. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.CC, nuovi lavori del giorno).
Categorie arXiv: Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2610.42138 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-02T07:45:45.705Z dalla pagina https://arxiv.org/list/cs.CC/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).