2026-07-21T23:34:00Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:6446 2024-03-06T10:38:17Z ddc:004 open_access

Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers Dose, Titus computational complexity constraint satisfaction problems integer expressions and circuits 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 N (resp., finite intervals over N) 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 L, P, NP, PSPACE, NEXP, and even Sigma_1, the class of c.e. languages. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Titus Dose 2016 Is Part Of LIPIcs, Volume 58, 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2016.32 urn:nbn:de:0030-drops-64461 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2016.32 eng https://creativecommons.org/licenses/by/3.0/legalcode