Border basis detection is NP-complete

DOI10.1145/1993886.1993895MaRDI QIDQ5254148zbMATH OpenOpenAlexWikidataFDO

Authors Ambedkar Dukkipati, Prabhanjan Ananth

Publication date 9 June 2015

Published in Proceedings of the 36th international symposium on Symbolic and algebraic computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1011.6021

zbMATH Keywords

border basescomplexityNP-completenesszero-dimensional ideals

Mathematics Subject Classification ID

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) Analysis of algorithms and problem complexity (68Q25) Symbolic computation and algebraic computation (68W30)

Abstract: Border basis detection (BBD) is described as follows: given a set of generators of an ideal, decide whether that set of generators is a border basis of the ideal with respect to some order ideal. The motivation for this problem comes from a similar problem related to Gr"obner bases termed as Gr"obner basis detection (GBD) which was proposed by Gritzmann and Sturmfels (1993). GBD was shown to be NP-hard by Sturmfels and Wiegelmann (1996). In this paper, we investigate the computational complexity of BBD and show that it is NP-complete.

Recommendations

• Complexity of Gröbner basis detection and border basis detection
• A signature based border basis algorithm
• Structural Gröbner basis detection
• Computing border bases
• A Polyhedral Characterization of Border Bases

Cited in

(4)

• Structural Gröbner basis detection
• Complexity of Gröbner basis detection and border basis detection
• A Polyhedral Characterization of Border Bases
• Computing border bases

This page was built for publication: Border basis detection is NP-complete

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5254148)