DIMACS Discrete Math/Theory of Computing Seminar


Title:

Hilbert's Nullstellensatz is in the Polynomial Hierarchy

Speaker:

Pascal Koiran

Place:

DIMACS Seminar Room 431, CoRE Building
Busch Campus, Rutgers University

Time:

4:30 PM
Tuesday, May 7, 1996

Abstract:

We show that 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).
dimacs-www@dimacs.rutgers.edu
Document last modified on April 30, 1996