Satisfaction of polynomial constraints over finite domains using function values

This paper shows how the solutions of constraint satisfac-tion problems that involve only polynomial constraints over finite do-mains can be enumerated by computing the values of related polynomial functions at appropriate points. The proposed algorithm first transforms constraints, which are expressed as equalities, inequalities, and disequal-ities of polynomials with integer coefficients and integer variables, into a canonical form that uses only inequalities. Then, starting from a bound-ing box, which is supposed to be known, the algorithm recursively sub-divides the box into disjoint boxes and it records boxes whose elements satisfy all constraints. The subdivision is driven by the study of the sign of polynomial functions over boxes, which is performed by means of a method that uses only the coefficients of polynomials and the values of functions at the corners of boxes.