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 natural numbers (resp., finite intervals over natural numbers) 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 $\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and even $\Sigma_1$, the class of c.e. languages.

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 natural numbers (resp., finite intervals over natural numbers) 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 $\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and even $\Sigma_1$, the class of c.e. languages.

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 natural numbers (resp., finite intervals over natural numbers) 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 $\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and even $\Sigma_1$, the class of c.e. languages.

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 natural numbers (resp., finite intervals over natural numbers) 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 $\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and even $\Sigma_1$, the class of c.e. languages.

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 natural numbers (resp., finite intervals over natural numbers) 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 $\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and even $\Sigma_1$, the class of c.e. languages.

Only spelling mistakes have been corrected.

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 natural numbers (resp., finite intervals over natural numbers) 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 $\mathrm{L}$, $\mathrm{P}$, $\mathrm{NP}$, $\mathrm{PSPACE}$, $\mathrm{NEXP}$, and even $\Sigma_1$, the class of c.e. languages.