ECCC-Report TR16-031https://eccc.weizmann.ac.il/report/2016/031Comments and Revisions published for TR16-031en-usThu, 02 Jun 2016 16:30:56 +0300
Revision 5
| Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers |
Titus Dose
https://eccc.weizmann.ac.il/report/2016/031#revision5We 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. Thu, 02 Jun 2016 16:30:56 +0300https://eccc.weizmann.ac.il/report/2016/031#revision5
Revision 4
| Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers |
Titus Dose
https://eccc.weizmann.ac.il/report/2016/031#revision4We 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. Fri, 06 May 2016 15:52:32 +0300https://eccc.weizmann.ac.il/report/2016/031#revision4
Revision 3
| Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers |
Titus Dose
https://eccc.weizmann.ac.il/report/2016/031#revision3We 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. Fri, 06 May 2016 15:48:17 +0300https://eccc.weizmann.ac.il/report/2016/031#revision3
Revision 2
| Complexity of Constraint Satisfaction Problems over Finite Substsets of Natural Numbers |
Titus Dose
https://eccc.weizmann.ac.il/report/2016/031#revision2We 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. Fri, 06 May 2016 15:44:48 +0300https://eccc.weizmann.ac.il/report/2016/031#revision2
Revision 1
| Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers |
Titus Dose
https://eccc.weizmann.ac.il/report/2016/031#revision1We 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. Thu, 10 Mar 2016 11:37:45 +0200https://eccc.weizmann.ac.il/report/2016/031#revision1
Paper TR16-031
| Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers |
Titus Dose
https://eccc.weizmann.ac.il/report/2016/031We 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. Wed, 09 Mar 2016 03:22:37 +0200https://eccc.weizmann.ac.il/report/2016/031