Complexity of Gröbner basis detection and border basis detection
| Autor: | Prabhanjan V. Ananth, Ambedkar Dukkipati |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Ideal (set theory) Mathematics::Commutative Algebra General Computer Science Computational complexity theory Basis (linear algebra) Gröbner basis detection Prove it Order (ring theory) Complexity Term (logic) Theoretical Computer Science Set (abstract data type) Zero-dimensional ideals Gröbner basis Border bases Computer Science(all) Mathematics |
| Zdroj: | Theoretical Computer Science. 459:1-15 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2012.08.002 |
| Popis: | Gröbner basis detection (GBD) is defined as follows: given a set of polynomials, decide whether there exists–and if “yes” find–a term order such that the set of polynomials is a Gröbner basis. This problem was proposed by Gritzmann and Sturmfels (1993) [12] and it was shown to be NP-hard by Sturmfels and Wiegelmann. We investigate the computational complexity of this problem when the given set of polynomials are the generators of a zero-dimensional ideal. Further, we propose the Border basis detection (BBD) problem which is formulated as follows: given a set of generators of an ideal, decide whether the set of generators is a border basis of the ideal with respect to some order ideal. We analyse the complexity of this problem and prove it to be NP-complete. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect