LIPIcs.MFCS.2016.32.pdf
- Filesize: 493 kB
- 13 pages
Document
Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers
Author
-
Part of:
Volume:
41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Mathematical Foundations of Computer Science (MFCS) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-08-19
Cite As Get BibTex
Titus Dose. Complexity of Constraint Satisfaction Problems over Finite Subsets of Natural Numbers. In 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 58, pp. 32:1-32:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.MFCS.2016.32
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 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.
Subject Classification
Keywords
- computational complexity
- constraint satisfaction problems
- integer expressions and circuits
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
E. Böhler, C. Glaßer, B. Schwarz, and K. W. Wagner. Generation problems. Theor. Comput. Sci., 345(2-3):260-295, 2005.
-
M. Davis, H. Putnam, and J. Robinson. The decision problem for exponential Diophantine equations. Annals of Mathematics, 74(2):425-436, 1961.
-
T. Dose. Complexity of constraint satisfaction problems over finite subsets of natural numbers. Technical Report 16-031, Electronic Colloquium on Computational Complexity (ECCC), 2016.
-
T. Feder and M. Y. Vardi. The computational structure of monotone monadic snp and constraint satisfaction: A study through datalog and group theory. SIAM J. Comput., 28(1):57-104, February 1999.
-
Christian Glaßer, Katrin Herr, Christian Reitwießner, Stephen D. Travers, and Matthias Waldherr. Equivalence problems for circuits over sets of natural numbers. Theory Comput. Syst., 46(1):80-103, 2010.
-
C. Glaßer, B. Martin, and P. Jonsson. Circuit satisfiability and constraint satisfaction problems around skolem arithmetic. In Proceedings of the 12th International Conference on Computability in Europe (CiE-2016), Lecture Notes in Computer Science. Springer Verlag, 2016. To appear.
-
C. Glaßer, C. Reitwießner, S. Travers, and M. Waldherr. Satisfiability of algebraic circuits over sets of natural numbers. Discrete Applied Mathematics, 158(13):1394 - 1403, 2010.
-
R. Greenlaw, H. J. Hoover, and W. L. Ruzzo. A Compendium of Problems Complete for P, 1991.
-
D. E. Knuth. All questions answered. Notices of the AMS, 49(3):318-324, 2002.
-
Y. V. Matiyasevich. Enumerable sets are Diophantine. Doklady Akad. Nauk SSSR, 191:279-282, 1970. Translation in Soviet Math. Doklady, 11:354-357, 1970.
-
Pierre McKenzie and Klaus W. Wagner. The complexity of membership problems for circuits over sets of natural numbers. Computational Complexity, 16(3):211-244, 2007.
-
C. M. Papadimitriou. Computational complexity. Addison-Wesley, Reading, Massachusetts, 1994.
-
Omer Reingold. Undirected connectivity in log-space. J. ACM, 55(4):17:1-17:24, September 2008.
-
L. J. Stockmeyer and A. R. Meyer. Word problems requiring exponential time: Preliminary report. In Proceedings of the Fifth Annual ACM Symposium on Theory of Computing, STOC '73, pages 1-9, New York, NY, USA, 1973. ACM.