# 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