Content deleted Content added
→Complexity: the constant factor is already implied by \Omega(n) |
TheMathCat (talk | contribs) m Link to journal added |
||
Line 25:
<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|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 optimal. Nevertheless, such examples are extremely rare.
| |||