Editing Buchberger's algorithm (section)

== Complexity ==
The [[time complexity|computational complexity]] of Buchberger's algorithm is very difficult to estimate, because of the number of choices that may dramatically change the computation time. Nevertheless, T. W. Dubé has proved<ref>{{cite journal|doi=10.1137/0219053|title=The Structure of Polynomial Ideals and Gröbner Bases|journal=SIAM Journal on Computing|volume=19|issue=4|pages=750–773|year=1990|last1=Dubé|first1=Thomas W.}}</ref> that the degrees of the elements of a reduced Gröbner basis are always bounded by
:<math>2\left(\frac{d^2}{2} +d\right)^{2^{n-2}}</math>,
where {{math|''n''}} is the number of variables, and {{math|''d''}} the maximal [[total degree]] of the input polynomials. This allows, in theory, to use [[linear algebra]] over the [[vector space]] of the polynomials of degree bounded by this value, for getting an algorithm of complexity
<math>d^{2^{n+o(1)}}</math>.

On the other hand, there are examples<ref>{{cite journal|doi=10.1016/0001-8708(82)90048-2|doi-access=free|title=The complexity of the word problems for commutative semigroups and polynomial ideals|journal=[[Advances in Mathematics]]|volume=46|issue=3|pages=305–329|year=1982|last1=Mayr|first1=Ernst W|last2=Meyer|first2=Albert R|hdl=1721.1/149010|hdl-access=free}}</ref> where the Gröbner basis contains elements of degree
:<math>d^{2^{\Omega(n)}}</math>,
and the above upper bound of complexity is optimal. Nevertheless, such examples are extremely rare.

Since its discovery, many variants of Buchberger's have been introduced to improve its efficiency. [[Faugère's F4 and F5 algorithms]] are presently the most efficient algorithms for computing Gröbner bases, and allow to compute routinely Gröbner bases consisting of several hundreds of polynomials, having each several hundreds of terms and coefficients of several hundreds of digits.