Border Basis Detection is NP-complete

被引：0

作者：

Ananth, Prabhanjan V. ^{[1
]}

Dukkipati, Ambedkar ^{[1
]}

机构：

[1] Indian Inst Sci, Dept Comp Sci & Automat, Bangalore, Karnataka, India

来源：

ISSAC 2011: PROCEEDINGS OF THE 36TH INTERNATIONAL SYMPOSIUM ON SYMBOLIC AND ALGEBRAIC COMPUTATION | 2011年

关键词：

Border bases; Zero-dimensional ideals; Complexity; NP-completeness; BASES;

D O I：

暂无

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

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 Grobner bases termed as Grobner 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.

引用

页码：11 / 18

页数：8

共 12 条

[1]

AUZINGER W, 1988, INT SCHRIFTENREIHE N, V86, P11

[2]

Braun G., 2010, ARXIV09121502V2

[3] MINKOWSKI ADDITION OF POLYTOPES - COMPUTATIONAL-COMPLEXITY AND APPLICATIONS TO GROBNER BASES [J].

GRITZMANN, P ;

STURMFELS, B .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1993, 6 (02) :246-269

[4]

Kehrein A, 2005, ALGORITHM COMP MATH, V14, P169

[5] Computing border bases [J].

Kehrein, A ;

Kreuzer, M .

JOURNAL OF PURE AND APPLIED ALGEBRA, 2006, 205 (02) :279-295

[6] Characterizations of border bases [J].

Kehrein, A ;

Kreuzer, M .

JOURNAL OF PURE AND APPLIED ALGEBRA, 2005, 196 (2-3) :251-270

[7]

Kreuzer M., 2005, Computational Commutative Algebra, V2

[8]

Mourrain B, 1999, LECT NOTES COMPUT SC, V1719, P430

[9]

Mourrain B., 2005, P INT S SYMB ALG COM, P253

[10] Stable normal forms for polynomial system solving [J].

Mourrain, Bernard ;

Trebuchet, Philippe .

THEORETICAL COMPUTER SCIENCE, 2008, 409 (02) :229-240

← 1 2 →