LIPIcs.CSL.2015.60.pdf
- Filesize: 471 kB
- 18 pages
Document
A Definability Dichotomy for Finite Valued CSPs
Authors
-
Part of:
Volume:
24th EACSL Annual Conference on Computer Science Logic (CSL 2015)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: Computer Science Logic (CSL) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2015-09-07
Cite AsGet BibTex
Anuj Dawar and Pengming Wang. A Definability Dichotomy for Finite Valued CSPs. In 24th EACSL Annual Conference on Computer Science Logic (CSL 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 41, pp. 60-77, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.CSL.2015.60
https://doi.org/10.4230/LIPIcs.CSL.2015.60
Abstract
Finite valued constraint satisfaction problems are a formalism for describing many natural optimisation problems, where constraints on the values that variables can take come with rational weights and the aim is to find an assignment of minimal cost. Thapper and Zivny have recently established a complexity dichotomy for valued constraint languages. They show that each such languages either gives rise to a polynomial-time solvable optimisation problem, or to an NP-hard one, and establish a criterion to distinguish the two cases. We refine the dichotomy by showing that all optimisation problems in the first class are definable in fixed-point language with counting, while all languages in the second class are not definable, even in infinitary logic with counting. Our definability dichotomy is not conditional on any complexity-theoretic assumption.
Keywords
- descriptive complexity
- constraint satisfaction
- definability
- fixed-point logic
- optimization
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
M. Anderson, A. Dawar, and B. Holm. Maximum matching and linear programming in fixed-point logic with counting. In Proceedings of the 28th Annual ACM/IEEE Symposium on Logic in Computer Science, pages 173-182, 2013.
-
A. Atserias, A. Bulatov, and A. Dawar. Affine systems of equations and counting infinitary logic. Theoretical Computer Science, 410(18):1666-1683, 2009.
-
L. Barto and M. Kozik. Constraint satisfaction problems solvable by local consistency methods. J. ACM, 61, 2014.
-
A. Bulatov, P. Jeavons, and A. Krokhin. Classifying the complexity of constraints using finite algebras. SIAM Journal on Computing, 34(3):720-742, 2005.
-
D. Cohen, M.C. Cooper, P. Jeavons, and A. Krokhin. The complexity of soft constraint satisfaction. Artificial Intelligence, 170(11):983-1016, 2006.
-
A. Dawar. The nature and power of fixed-point logic with counting. ACM SIGLOG News, 2:8-21, 2015.
-
H-D. Ebbinghaus and J. Flum. Finite Model Theory. Springer, 2nd edition, 1999.
-
T. Feder and M.Y. Vardi. Computational structure of monotone monadic SNP and constraint satisfaction: A study through Datalog and group theory. SIAM Journal on Computing, 28:57-104, 1998.
-
A. Huber, A. Krokhin, and R. Powell. Skew bisubmodularity and valued CSPs. SIAM Journal on Computing, 43(3):1064-1084, 2014.
-
L. Libkin. Elements of Finite Model Theory. Springer, 2004.
-
M. Otto. Bounded Variable Logics and Counting - A Study in Finite Models, volume 9 of Lecture Notes in Logic. Springer-Verlag, 1997.
-
J. Thapper and S. Živný. The complexity of finite-valued CSPs. In Proceedings of the 45th ACM Symposium on the Theory of Computing, STOC'13, pages 695-704. ACM, 2013.