On Polynominal Ideals, Their Complexity, and Applications
A polynomial ideal membership problem is a (w+1)-tuple
P=(f,g1,g2,...,gw+1) where f and the
gi are multivariate polynomials over some ring, and the problem is
to determine whether f is in the ideal generated by the gi. For
polynomials over the integers or rationals, it is known that this problem is
exponential space complete. We discuss complexity results known for a number of
problems related to polynomial ideals, like the word problem for
commutative semigroups, a quantitative version of Hilbert's
Nullstellensatz, and the reachability and other problems for
(reversible) Petri nets.
