Content deleted Content added
TheMathCat (talk | contribs) doi access for a ref |
m Open access bot: hdl updated in citation with #oabot. |
||
Line 30:
<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.
| |||