On the Complexity of Hilbert's Nullstellensatz over Positive
4Aug (Fri), 2017
11am to 11:45am
An important problem in computational algebraic geometry is to decide if
there exists a common solution of a given set of multivariate
polynomials over an algebraically closed field. This decision problem is
also known as Hilbert's Nullstellensatz (HN). The complexity of HN over
arbitrary characteristic fields is known to be in PSPACE. Over zero
characteristic, this problem is shown to be in AM by Koiran (1996) under
the assumption that "Generalized Riemann Hypothesis" is true. We are
interested in HN over positive characteristic fields.
We divide the problem in two cases: first, when the dimension of the
given system of polynomial equations is positive and second, when the
dimension of the given system of polynomial equations is zero.
In positive dimensional case, we solve three special cases in NP. First
case is when the zero set of the given affine or projective system is
either empty or absolutely irreducible. Second when the zero set of
given affine system is either empty or one of its absolutely irreducible
component of same dimension is definable in the coefficient field of the
system. Third case is when the zero set of given projective system is
either empty or one of its absolutely irreducible component of same
dimension is definable in the coefficient field of the system such that
the product of the degree of polynomials defining the component, is not
more than the product of the degree of the given polynomials.
In zero dimensional case, we construct an affine system which have no
small zeros. Further, we give a reduction of affine zero dimensional
systems to affine positive dimensional systems making general affine
positive dimensional case at least as hard as affine zero dimensional case.