On Poynomial Ideals, Their Complexity, and Applications

A polynomial ideal membership problem is a (w+1)-tuple P=(f,g_1,g_2,...,g_{w+1}) where f and the g_i are multivariate polynomials over some ring, and the problem is to determine whether f is in the ideal generated by the g_i. 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.     «

A polynomial ideal membership problem is a (w+1)-tuple P=(f,g_1,g_2,...,g_{w+1}) where f and the g_i are multivariate polynomials over some ring, and the problem is to determine whether f is in the ideal generated by the g_i. 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...     »