Content deleted Content added
→Complexity: changed 2^(n-1) to 2^(n-2), from page 26 of Dub90 as cited in [1] |
→Complexity: the constant factor is already implied by \Omega(n) |
||
Line 27:
On the other hand, there are examples<ref>{{cite journal|doi=10.1016/0001-8708(82)90048-2|title=The complexity of the word problems for commutative semigroups and polynomial ideals|journal=Advances in Mathematics|volume=46|issue=3|pages=305|year=1982|last1=Mayr|first1=Ernst W|last2=Meyer|first2=Albert R}}</ref> where the Gröbner basis contains elements of degree
:<math>d^{2^{\Omega(n)}}</math>,
and the above upper bound of complexity is
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.
| |||