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 条
  • [1] ON THE COMPLEXITY OF COMPUTING CRITICAL POINTS WITH GROBNER BASES
    Spaenlehauer, Pierre-Jean
    SIAM JOURNAL ON OPTIMIZATION, 2014, 24 (03) : 1382 - 1401
  • [2] Computing strong regular characteristic pairs with Grobner bases
    Dong, Rina
    Wang, Dongming
    JOURNAL OF SYMBOLIC COMPUTATION, 2021, 104 : 312 - 327
  • [3] CONSTRUCTING SCN BASES IN CHARACTERISTIC-2
    POLI, A
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1995, 41 (03) : 790 - 794
  • [4] On the complexity of computing Grobner bases for weighted homogeneous systems
    Faugere, Jean-Charles
    El Din, Mohab Safey
    Verron, Thibaut
    JOURNAL OF SYMBOLIC COMPUTATION, 2016, 76 : 107 - 141
  • [5] Grobner bases for finite-temperature quantum computing and their complexity
    Crompton, P. R.
    JOURNAL OF MATHEMATICAL PHYSICS, 2011, 52 (11)
  • [6] On the arithmetic complexity of computing Grobner bases of comaximal determinantal ideals
    Gopalakrishnan, Sriram
    JOURNAL OF ALGEBRA, 2025, 668 : 233 - 264
  • [7] Grobner bases as characteristic sets
    Ferro, GC
    GEOMETRIC AND COMBINATORIAL ASPECTS OF COMMUNTATIVE ALGEBRA, 2001, 217 : 99 - 110
  • [8] On the complexity of Grobner bases conversion
    Kalkbrener, M
    JOURNAL OF SYMBOLIC COMPUTATION, 1999, 28 (1-2) : 265 - 273
  • [9] Computing inhomogeneous Grobner bases
    Bigatti, A. M.
    Caboara, M.
    Robbiano, L.
    JOURNAL OF SYMBOLIC COMPUTATION, 2011, 46 (05) : 498 - 510
  • [10] A NEW FRAMEWORK FOR COMPUTING GROBNER BASES
    Gao, Shuhong
    Volny, Frank
    Wang, Mingsheng
    MATHEMATICS OF COMPUTATION, 2015, 85 (297) : 449 - 465
12345