Let $𝐾$ be a ring and $𝐾[{𝑥}_0,\dots ,{𝑥}_{𝑛}]$ a polynomial ring over it. Suppose $𝐼\subset 𝐾[{𝑥}_0,\dots ,{𝑥}_{𝑛}]$ is an ideal. A Gröbner basis for $𝐼$ is a generating set of polynomials for the ideal that is minimal with respect to a given ordering on the monomials ${𝑥}_0,\dots ,{𝑥}_{𝑛}$.

Given an ideal $𝐼$, a Gröbner basis for $𝐼$ may be found via Buchberger’s algorithm. Intuitively, Buchberger’s algorithm attempts to solve a system of polynomial equations by iterated polynomial division to eliminate variables. At any given point, there is a degree of freedom in which what variable will be eliminated by the next division. The algorithm attempts to eliminate variables with respect to the monomial ordering.

Buchberger’s algorithm may be viewed simultaneously as a generalization of the Quine-McCluskey Boolean minimization algorithm and as a special case of the Knuth-Bendix algorithm.

The complexity of Buchberger’s algorithm is a little unwieldy to estimate in general. However, just like SAT solvers there are enough optimizations to execute Buchberger reasonably fast in practice. For instance, it is fast enough to handle several hundreds of polynomials, each having hundreds of terms with very large coefficients.

There are some very fun applications of this approach, such as Solving Sudoku with Algebra. This idea has also been applied to inferring polynomial loop invariants.