A subdivision approach to the solution of polynomial constraints over finite domains using the modified Bernstein form

This paper discusses an algorithm to solve polynomial constraints over finite domains, namely constraints which are expressed in terms of equalities, inequalities and disequalities of polynomials with integer coefficients whose variables are associated with finite domains. The proposed algorithm starts with a preliminary step intended to rewrite all constraints to a canonical form. Then, the modified Bernstein form of obtained polynomials is used to recursively restrict the domains of variables, which are assumed to be initially approximated by a bounding box. The proposed algorithm proceeds by subdivisions, and it ensures that each variable is eventually associated with the inclusion maximal finite domain in which the set of constraints is satisfiable. If arbitrary precision integer arithmetic is available, no approximation is introduced in the solving process because the coefficients of the modified Bernstein form are integer numbers.