ON THE COMPLEXITY OF COMPUTING GROBNER BASES IN CHARACTERISTIC-2

被引：0
|
作者：
ACCIARO, V
机构：
[1] School of Computer Science, Carleton University, Ottawa
来源：
INFORMATION PROCESSING LETTERS | 1994年 / 51卷 / 06期
关键词：
COMPUTATIONAL COMPLEXITY; ANALYSIS OF ALGORITHMS;
D O I：
10.1016/0020-0190(94)00106-5
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
The computation of a Grobner basis over a field F is characterized by a space complexity which grows doubly exponentially with the number of variables. Existing proofs of this fact use nonelementary results from commutative algebra and algebraic geometry. In this paper we use an elementary argument to show that, when char(F) = 2, and the number of variables is unbounded, the problem of computing a Grobner basis is NP-hard.
引用
收藏
页码：321 / 323
页数：3
相关论文
共 50 条
  • [21] A NOTE ON THE COMPLEXITY OF CONSTRUCTING GROBNER-BASES
    BUCHBERGER, B
    LECTURE NOTES IN COMPUTER SCIENCE, 1983, 162 : 137 - 145
  • [22] A HYBRID GROBNER BASES APPROACH TO COMPUTING POWER INTEGRAL BASES
    Robertson, L.
    Russell, R.
    ACTA MATHEMATICA HUNGARICA, 2015, 147 (02) : 427 - 437
  • [23] Computing homology using generalized Grobner bases
    Hall, Becky Eide
    JOURNAL OF SYMBOLIC COMPUTATION, 2013, 54 : 59 - 71
  • [24] Opal: A system for computing noncommutative Grobner bases
    Green, EL
    Heath, LS
    Keller, BJ
    REWRITING TECHNIQUES AND APPLICATIONS, 1997, 1232 : 331 - 334
  • [25] Towards a certified and efficient computing of Grobner bases
    Jorge, JS
    Gulías, VM
    Freire, JL
    Sánchez, JJ
    COMPUTER AIDED SYSTEMS THEORY - EUROCAST 2005, 2005, 3643 : 111 - 120
  • [26] COMPUTING GROBNER BASES AND INVARIANTS OF THE SYMMETRIC ALGEBRA
    La Barbiera, M.
    Restuccia, G.
    MISKOLC MATHEMATICAL NOTES, 2017, 17 (02) : 777 - 789
  • [27] Computing generic bivariate Grobner bases with MATHEMAGIX
    Larrieu, Robin
    ACM COMMUNICATIONS IN COMPUTER ALGEBRA, 2019, 53 (02): : 41 - 44
  • [28] On computing Grobner bases in rings of differential operators
    Ma XiaoDong
    Sun Yao
    Wang DingKang
    SCIENCE CHINA-MATHEMATICS, 2011, 54 (06) : 1077 - 1087
  • [29] Computing Grobner Bases within Linear Algebra
    Suzuki, Akira
    COMPUTER ALGEBRA IN SCIENTIFIC COMPUTING, PROCEEDINGS, 2009, 5743 : 310 - 321
  • [30] An efficient method for computing comprehensive Grobner bases
    Kapur, Deepak
    Sun, Yao
    Wang, Dingkang
    JOURNAL OF SYMBOLIC COMPUTATION, 2013, 52 : 124 - 142
12345