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

DOI10.1137/0215042MaRDI QIDQ3740228zbMATH OpenOpenAlexFDO

Authors 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

algebraic manipulationcommutative semigroupNP-hard

Mathematics Subject Classification ID

Ideals and multiplicative ideal theory in commutative rings (13A15) Polynomial rings and ideals; rings of integer-valued polynomials (13F20) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Recommendations

• Complexity of membership problems of different types of polynomial ideals
• Membership in polynomial ideals over \(\mathcal{Q}\) is exponential space complete
• Some complexity results for polynomial ideals
• On polynomial ideals, their complexity, and applications
• The membership problem for unmixed polynomial ideals is solvable in single exponential time

Cited in

(9)

• Some complexity bounds for problems concerning finite and 2-dimensional vector addition systems with states
• Some complexity results for polynomial ideals
• Complexity of membership problems of different types of polynomial ideals
• The Complexity of the Ideal Membership Problem for Constrained Problems Over the Boolean Domain
• scientific article; zbMATH DE number 7559384 (Why is no real title available?)
• Membership in polynomial ideals over \(\mathcal{Q}\) is exponential space complete
• Ideal membership problem over 3-element CSPs with dual discriminator polymorphism
• The complexity of the ideal membership problem for constrained problems over the Boolean domain
• The Monomial Ideal Membership Problem and Polynomial Identity Testing

This page was built for publication: The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3740228)