Complexity of Membership Problems of Different Types of Polynomial Ideals

DOI10.1007/978-3-319-70566-8_20zbMath1402.13025OpenAlexW2789905105MaRDI QIDQ4556588

Stefan Toman, Ernst W. Mayr

Publication date: 16 November 2018

Published in: Algorithmic and Experimental Methods in Algebra, Geometry, and Number Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-70566-8_20

zbMATH Keywords

computational complexityGröbner basisdegree boundbinomial idealradicalcellular decompositionpolynomial idealThue system

Mathematics Subject Classification ID

Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Lattice ideals, congruence relations (06B10) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Word problems, etc. in computability and recursion theory (03D40) Thue and Post systems, etc. (03D03) Word problems (aspects of algebraic structures) (08A50)

Related Items (2)

Dehn functions of finitely presented metabelian groups ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A new lower bound construction for commutative Thue systems with applications
• Bounds for the degrees in the Nullstellensatz
• The membership problem for unmixed polynomial ideals is solvable in single exponential time
• Some complexity results for polynomial ideals
• Efficient computation of zero-dimensional Gröbner bases by change of ordering
• Radicals of binomial ideals
• The complexity of the word problems for commutative semigroups and polynomial ideals
• Optimal algorithms for the coverability, the subword, the containment, and the equivalence problems for commutative semigroups.
• Binomial ideals
• Dimension-dependent bounds for Gröbner bases of polynomial ideals
• An algorithm for the computation of the radical of an ideal
• The Structure of Polynomial Ideals and Gröbner Bases
• Sharp Effective Nullstellensatz
• Space-efficient Gröbner basis computation without degree bounds
• An optimal algorithm for constructing the reduced Gröbner basis of binomial ideals, and applications to commutative semigroups

This page was built for publication: Complexity of Membership Problems of Different Types of Polynomial Ideals