Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



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

RSS-Feed

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: 796
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: 739
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: 745
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: 807
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


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