2010/11/28 by Prabhanjan Ananth, Prabhanjan V. Ananth, Ananth, Prabhanjan V. +2
Computer Science · Engineering · Mathematics · #Advanced Numerical Analysis Techniques #Commutative Algebra and Its Applications #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Polynomial and algebraic computation #cs.CC
paper · pdf · doi:10.48550/arxiv.1011.6021
18 pages
arxiv created 2010/11/28 · openalex publication_date 2010/11/28 · arxiv updated 2010/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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öbner bases termed as Gröbner 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.