Hilbert's Nullstellensatz is in the Counting Hierarchy
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2026
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866915809060716544 |
|---|---|
| author | Andrews, Robert Garg, Abhibhav Schost, Éric |
| author_facet | Andrews, Robert Garg, Abhibhav Schost, Éric |
| contents | We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, lies in the counting hierarchy. More generally, we show that the number of solutions to a system of equations can be computed in polynomial time with oracle access to the counting hierarchy. Our results hold in particular for polynomials with coefficients in either the rational numbers or a finite field. Previously, the best-known bounds on the complexities of these problems were PSPACE and FPSPACE, respectively. Our main technical contribution is the construction of a uniform family of constant-depth arithmetic circuits that compute the multivariate resultant. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_17904 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hilbert's Nullstellensatz is in the Counting Hierarchy Andrews, Robert Garg, Abhibhav Schost, Éric Computational Complexity Symbolic Computation We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, lies in the counting hierarchy. More generally, we show that the number of solutions to a system of equations can be computed in polynomial time with oracle access to the counting hierarchy. Our results hold in particular for polynomials with coefficients in either the rational numbers or a finite field. Previously, the best-known bounds on the complexities of these problems were PSPACE and FPSPACE, respectively. Our main technical contribution is the construction of a uniform family of constant-depth arithmetic circuits that compute the multivariate resultant. |
| title | Hilbert's Nullstellensatz is in the Counting Hierarchy |
| topic | Computational Complexity Symbolic Computation |
| url | https://arxiv.org/abs/2602.17904 |