Abstract / Description of output
We show how the complexity of counting relates to the well known phenomenon that computing Gröbner bases under a lexicographic order is generally harder than total degree orders. We give simple examples of polynomials for which it is very easy to compute their Gröbner basis using a total degree order but for which exponential time is required for a lexicographic order. It follows that conversion algorithms do not help in such cases.
| Original language | English |
|---|---|
| Pages (from-to) | 307-313 |
| Number of pages | 7 |
| Journal | Journal of Symbolic Computation |
| Volume | 31 |
| Issue number | 3 |
| DOIs | |
| Publication status | Published - Mar 2001 |