|
NeuroCOLT
Technical Report NC-TR-96-044
Hilbert's Nullstellensatz
is in the Polynomial Hierarchy
Pascal
Koiran
Ecole Normale Superieure de Lyon
France
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. The best previous bound was PSPACE. The possibility that
this problem might be NP-complete is also discussed (it is well-known
to be NP-hard).
Download Compressed
Postscript
|