The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals

DOI10.1137/0215042zbMath0603.68038MaRDI QIDQ3740228

Dung T. Huynh

Publication date: 1986

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0215042

zbMATH Keywords

NP-hard; commutative semigroup; algebraic manipulation

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

68W30: Symbolic computation and algebraic computation

13F20: Polynomial rings and ideals; rings of integer-valued polynomials

13A15: Ideals and multiplicative ideal theory in commutative rings

Related Items

Membership in polynomial ideals over Q is exponential space complete, Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states