The Hilbert zonotope and a polynomial time algorithm for universal Gröbner bases. (Q1408266): Difference between revisions

The computation of a Gröbner basis is one of the fundamental algorithmic processes in polynomial ideal theory. Unfortunately, this process depends exponentially on the number of variables. Considering a fixed number \(d\) of variables, the authors show that a universal Gröbner basis for an ideal \(I\) in the multivariate polynomial ring \(F[x]\) can be computed in time depending polynomially on \(n\), the \(F\)-dimension of \(F[x]/I\). Of course, \(d\) enters exponentially in the complexity bound, which could be stated a bit more prominently in the title and abstract.