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).

Document last modified on April 30, 1996