Buchberger's algorithm: Difference between revisions

Revision as of 18:37, 13 December 2022

Revision as of 11:30, 18 August 2023

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|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.