Complexity of Gröbner basis detection and border basis detection
From MaRDI portal
Publication:1758159
DOI10.1016/j.tcs.2012.08.002zbMath1258.13029OpenAlexW2048364901MaRDI QIDQ1758159
Prabhanjan V. Ananth, Ambedkar Dukkipati
Publication date: 8 November 2012
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.tcs.2012.08.002
Gröbner bases; other bases for ideals and modules (e.g., Janet and border bases) (13P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A simplified NP-complete satisfiability problem
- Computing border bases
- A new efficient algorithm for computing Gröbner bases \((F_4)\)
- Structural Gröbner basis detection
- Computing Gröbner bases by FGLM techniques in a non-commutative setting
- Characterizations of border bases
- Stable normal forms for polynomial system solving
- Bruno Buchberger's PhD thesis 1965: An algorithm for finding the basis elements of the residue class ring of a zero dimensional polynomial ideal. Translation from the German
- A new incremental algorithm for computing Groebner bases
- A superexponential lower bound for Gröbner bases and Church-Rosser commutative thue systems
- Lifting standard bases in filtered structures
- Minkowski Addition of Polytopes: Computational Complexity and Applications to Gröbner Bases
- Membership in polynomial ideals over Q is exponential space complete
- Border basis detection is NP-complete
- Generalized normal forms and polynomial system solving
- Advances in Cryptology - CRYPTO 2003
- A Polyhedral Characterization of Border Bases
