Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers
Titus Dose · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2016
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.