# Hilbert's Nullstellensatz Is in the Polynomial Hierarchy

@article{Koiran1996HilbertsNI, title={Hilbert's Nullstellensatz Is in the Polynomial Hierarchy}, author={Pascal Koiran}, journal={J. Complex.}, year={1996}, volume={12}, pages={273-286} }

We show that if the Generalized Riemann Hypothesis is true, the problem of deciding whether a system of polynomial equations in several complex variables has a solution is in the second level of the polynomial hierarchy. In fact, this problem is in AM, the ``Arthur-Merlin'''' class (recall that $\np \subseteq \am \subseteq \rp^{\tiny \np} \subseteq \Pi_2$). The best previous bound was PSPACE. An earlier version of this paper was distributed as NeuroCOLT Technical Report~96-44. The present paper… Expand

#### Topics from this paper

#### 95 Citations

The Multivariate Resultant Is NP-hard in Any Characteristic

- Mathematics, Computer Science
- MFCS
- 2010

The main result is that testing the resultant for zero is NP-hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). Expand

On the complexity of the multivariate resultant

- Computer Science, Mathematics
- J. Complex.
- 2013

This paper investigates the complexity of computing the multivariate resultant and shows that this problem is NP-hard under deterministic reductions in any characteristic, for systems of low-degree polynomials with coefficients in the ground field (rather than in an extension). Expand

Dedekind Zeta Functions and the Complexity of Hilbert's Nullstellensatz

- Mathematics
- 2003

Let HN denote the problem of determining whether a system of multivariate polynomials with integer coefficients has a complex root. It has long been known that HN in P implies P=NP and, thanks to… Expand

Elimination of Parameters in the Polynomial Hierarchy

- Computer Science, Mathematics
- Theor. Comput. Sci.
- 1999

The present paper updates a technical report (LIP Research Report 97-37) with the same title, and in particular includes new results on interactive protocols and boolean parts. Expand

Dedekind Zeta Zeroes and Faster Complex Dimension Computation

- Computer Science, Mathematics
- ArXiv
- 2018

A minimalist hypothesis is derived that allows failures of GRH but still enable complex dimension computation in the polynomial hierarchy, and more plausible hypotheses are explored yielding the same speed-up. Expand

On the Structure of Valiant's Complexity Classes

- Mathematics, Computer Science
- Discret. Math. Theor. Comput. Sci.
- 1999

It is shown that if Valiant's hypothesis is true, then there is a p -definable family, which is neither p -computable nor VNP -complete, and defined relativized complexity classes VP h and VNP h and construct complete families in these classes. Expand

Algebraic dependencies and PSPACE algorithms in approximative complexity

- Mathematics, Computer Science
- Electron. Colloquium Comput. Complex.
- 2018

It is shown that APS is NP-hard and, using projective algebraic-geometry ideas,APS is put in PSPACE (prior best was EXPSPACE via Grobner basis computation). Expand

On the Complexity of Hilbert’s Nullstellensatz over Positive Characteristic

- 2017

Hilbert’s Nullstellensatz (HN) is a fundamental theorem in Algebraic Geometry. It establishes a fundamental relationship between geometry and algebra. If a given system of polynomial equations f1, .… Expand

Algebraic Geometry Over Four Rings and the Frontier to Tractability

- Mathematics
- 2000

We present some new and recent algorithmic results concerning polynomial system solving over various rings. In particular, we present some of the best recent bounds on: (a) the complexity of… Expand

A Direct Ultrametric Approach to Additive Complexity and the Shub-Smale Tau Conjecture

- Mathematics, Computer Science
- ArXiv
- 2003

Two weak versions of the Tau Conjecture are proved and it is shown that the Tauconjecture follows from an even more plausible hypothesis, which immediately implies the same bound on the number of ordinary rational roots. Expand

#### References

SHOWING 1-10 OF 36 REFERENCES

On The Intractability Of Hilbert's Nullstellensatz And An Algebraic Version Of . .

- Mathematics
- 1995

Section 1. Introduction In this paper we relate an elementary problem in number theory to the intractability of deciding whether an algebraic set defined over the complex numbers (or any… Expand

Some algebraic and geometric computations in PSPACE

- Mathematics, Computer Science
- STOC '88
- 1988

A PSPACE algorithm for determining the signs of multivariate polynomials at the common zeros of a system of polynomial equations is given and it is shown that the existential theory of the real numbers can be decided in PSPACE. Expand

Sharp effective Nullstellensatz

- Mathematics
- 1988

The usual proofs of this result, however, give no information about the g1's; for instance they give no bound on their degrees. This question was first considered by G. Hermann [H]. She used… Expand

On the Intrinsic Complexity of Elimination Theory

- Computer Science, Mathematics
- J. Complex.
- 1993

The intrinsic complexity of selected algorithmic problems of classical elimination theory in algebraic geometry is considered and reductions of fundamental questions of elimination theory to NP- and P#-complete problems are given and it is confirmed that some of these questions may have exponential size outputs. Expand

Every Prime has a Succinct Certificate

- Mathematics, Computer Science
- SIAM J. Comput.
- 1975

It remains an open problem whether a prime n can be recognized in only $\log _2^\alpha n$ operations of a Turing machine for any fixed $\alpha $. Expand

Does co-NP Have Short Interactive Proofs?

- Mathematics, Computer Science
- Inf. Process. Lett.
- 1987

It is proved that if the complexity class co -NP is contained in IP[k] for some constant k, then the polynomial-time hierarchy collapses to the second level and if the Graph Isomorphism problem is NP-complete, then this hierarchy collapses. Expand

Computing in Algebraic Extensions

- Mathematics
- 1983

The aim of this chapter is an introduction to elementary algorithms in algebraic extensions, mainly over Q and, to some extent, over GF(p). We will talk about arithmetic in Q(α) and GF(p n ) in… Expand

On Approximation Algorithms for #P

- Mathematics, Computer Science
- SIAM J. Comput.
- 1985

Any function in Valiant’s class P can be approximated to within any constant factor by a function in the class $\Delta _3^p $ of the polynomial-time, hierarchy. Expand

Precise sequential and parallel complexity bounds for quantifier elimination over algebraically closed fields

- Mathematics
- 1990

Abstract This paper deals mainly with fast quantifier elimination in the elementary theory of algebraically closed fields of any characteristic. It is subdivided into an introduction, a short… Expand

On a theory of computation and complexity over the real numbers: $NP$- completeness, recursive functions and universal machines

- Mathematics
- 1989

We present a model for computation over the reals or an arbitrary (ordered) ring R. In this general setting, we obtain universal machines, partial recursive functions, as well as JVP-complete… Expand