2026-08-10T15:59:53Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10025 2024-03-06T10:26:57Z ddc:004 open_access

The Constraint Satisfaction Problem: Complexity and Approximability (Dagstuhl Seminar 18231) Grohe, Martin Guruswami, Venkatesan Zivny, Stanislav Constraint satisfaction problem (CSP); Computational complexity; CSP dichotomy conjecture; Hardness of approximation; Unique games conjecture; Parameterised complexity; Descriptive complexity; Universal algebra; Logic; Semidefinite programming Constraint satisfaction has always played a central role in computational complexity theory; appropriate versions of CSPs are classical complete problems for most standard complexity classes. CSPs constitute a very rich and yet sufficiently manageable class of problems to give a good perspective on general computational phenomena. For instance, they help to understand which mathematical properties make a computational problem tractable (in a wide sense, e.g., polynomial-time solvable, non-trivially approximable, fixed-parameter tractable, or definable in a weak logic). In the last decade, research activity in this area has significantly intensified and hugely impressive progress was made. The Dagstuhl Seminar 18231 "The Constraint Satisfaction Problem: Complexity and Approximability" was aimed at bringing together researchers using all the different techniques in the study of the CSP so that they can share their insights obtained during the past three years. This report documents the material presented during the course of the seminar. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Martin Grohe and Venkatesan Guruswami and Stanislav Zivny 2018 Is Part Of Dagstuhl Reports, Volume 8, Issue 6 (2019) Article Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/DagRep.8.6.1 urn:nbn:de:0030-drops-100251 https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.6.1 eng https://creativecommons.org/licenses/by/3.0/legalcode