DIMACS TR: 96-27
Hilbert's Nullstellensatz is in the Polynomial Hierarchy
Author: Pascal Koiran
ABSTRACT
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