Hilbert's Nullstellensatz is in the Counting Hierarchy

Robert Andrews, Abhibhav Garg, Éric Schost

We show that Hilbert's Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, li…