Content deleted Content added
m Typo fixing, replaced: Simluation → Simulation |
→Complexity: changed 2^(n-1) to 2^(n-2), from page 26 of Dub90 as cited in [1] |
||
Line 21:
== 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|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-
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>.
| |||