Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #5 to TR16-031 | 2nd June 2016 16:30

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

Revision #5
Authors: Titus Dose
Accepted on: 2nd June 2016 16:30
Downloads: 544
Keywords:

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

Revision #4
Authors: Titus Dose
Accepted on: 6th May 2016 15:52
Downloads: 571
Keywords:

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

Revision #3
Authors: Titus Dose
Accepted on: 6th May 2016 15:48
Downloads: 526
Keywords:

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

Revision #2
Authors: Titus Dose
Accepted on: 6th May 2016 15:44
Downloads: 490
Keywords:

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

Revision #1
Authors: Titus Dose
Accepted on: 10th March 2016 11:37
Downloads: 589
Keywords:

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

TR16-031
Authors: Titus Dose
Publication: 9th March 2016 03:22
Downloads: 755
Keywords:

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.

ISSN 1433-8092 | Imprint