Home | Quick Search | Advanced Search | Bibliography submission | Bibliography submission using bibtex | Bibliography submission using bibtex file | Links | Help | Internal


TitleComplexity of Gröbner basis detection and border basis detection
Author(s) Prabhanjan V. Ananth, Ambedkar Dukkipati
TypeArticle in Journal
AbstractGrö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.
KeywordsBorder bases, Zero-dimensional ideals, Gröbner basis detection, Complexity
URL http://www.sciencedirect.com/science/article/pii/S0304397512007505
JournalTheoretical Computer Science
Pages1 - 15
Translation No
Refereed No