摘要：We study the computational complexity of constraint satisfaction problems that are based on integer expressions and algebraic circuits. On input of a finite set of variables and a finite set of constraints the question is whether the variables can be mapped onto finite subsets of N (resp., finite intervals over N) such that all constraints are satisfied. According to the operations allowed in the constraints, the complexity varies over a wide range of complexity classes such as L, P, NP, PSPACE, NEXP, and even Sigma_1, the class of c.e. languages.
关键词：computational complexity; constraint satisfaction problems; integer expressions and circuits
