### Revision(s):

__
Revision #5 to TR16-031 | 2nd June 2016 16:30
__
#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

**Abstract:**
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.

__
Revision #4 to TR16-031 | 6th May 2016 15:52
__
#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

**Abstract:**
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.

__
Revision #3 to TR16-031 | 6th May 2016 15:48
__
#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

**Abstract:**
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.

__
Revision #2 to TR16-031 | 6th May 2016 15:44
__
#### Complexity of Constraint Satisfaction Problems over Finite Substsets of Natural Numbers

**Abstract:**
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.

__
Revision #1 to TR16-031 | 10th March 2016 11:37
__
#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

**Abstract:**
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.

**Changes to previous version:**
Only spelling mistakes have been corrected.

### Paper:

__
TR16-031 | 7th March 2016 14:54
__

#### Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers

**Abstract:**
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.