Membership in polynomial ideals over Q is exponential space complete

DOI10.1007/BFb0029002zbMath1492.68065OpenAlexW1580599742MaRDI QIDQ5096173

No author found.

Publication date: 16 August 2022

Published in: STACS 89 (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bfb0029002

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational aspects of associative rings (general theory) (16Z05)

Related Items (10)

On polynomial ideals, their complexity, and applications ⋮ Ideal Membership Problem over 3-Element CSPs with Dual Discriminator Polymorphism ⋮ The Monomial Ideal Membership Problem and Polynomial Identity Testing ⋮ A hierarchy of proof rules for checking positive invariance of algebraic and semi-algebraic sets ⋮ Complexity of Gröbner basis detection and border basis detection ⋮ Unnamed Item ⋮ Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals ⋮ On the parallel complexity of the polynomial ideal membership problem ⋮ Practical complexities of probabilistic algorithms for solving Boolean polynomial systems ⋮ Discovering non-terminating inputs for multi-path polynomial programs

Cites Work

• Complexity of parallel matrix computations
• The complexity of the word problems for commutative semigroups and polynomial ideals
• The Complexity of the Membership Problem for Two Subclasses of Polynomial Ideals
• Fast Parallel Matrix Inversion Algorithms
• Constructions in Algebra
• Parallelism in random access machines
• Constructive Aspects of Noetherian Rings

This page was built for publication: Membership in polynomial ideals over Q is exponential space complete