Carleton University
Technical Report TR-232
December 1993
On the Complexity of Computing Gröbner Bases in Characteristic 2
Vincenzo Acciaro
Abstract
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 Grabner basis is NP-hard.