DIMACS TR: 96-27

Hilbert's Nullstellensatz is in the Polynomial Hierarchy

Author: Pascal Koiran


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 includes in particular a new lower bound for unsatisfiable systems, and remarks on the Arthur-Merlin class.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/1996/96-27.ps.gz

DIMACS Home Page