Membership in polynomial ideals over Q is exponential space complete

DOI10.1007/BFb0029002zbMath1492.68065MaRDI 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

68Q25: Analysis of algorithms and problem complexity

13P10: Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases)

16Z05: Computational aspects of associative rings (general theory)

Related Items

Unnamed Item, 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, On the parallel complexity of the polynomial ideal membership problem, Complexity of Gröbner basis detection and border basis detection, Practical complexities of probabilistic algorithms for solving Boolean polynomial systems, Fast Gröbner basis computation and polynomial reduction for generic bivariate ideals, 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