Counting and Grobner Bases

摘要

We show how the complexity of counting relates to the well known phenomenon that computing Grobner 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 Grobner 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.