Some Complexity Results for Polynomial Ideals
In this paper, we survey some of our new results on the complexity of a
number of problems related to polynomial ideals. We consider multivariate
polynomials over some ring, like the integers or the rationals. For instance,
a polynomial ideal membership problem is a (w+1)-tuple
P=(f,g1,g2,...,gw) where f and the
gi are multivariate
polynomials, and the problem is to determine whether f is in the ideal
generated by the gi. For polynomials over the integers or rationals,
this problem is known to be exponential space complete. We discuss further
complexity results for problems related to polynomial ideals, like the word
and subword problems for commutative semigroups, a quantitative version of
Hilbert's Nullstellensatz in a complexity theoretic version, and problems
concerning the computation of reduced polynomials and Gröbner bases.
These bounds provide the first exact complexity bounds for Gröbner
basis computation and for the representation of the state set of
reversible Petri nets.
