Options
Promise and infinite-domain constraint satisfaction
Publikationstyp
Conference Paper
Date Issued
2024
Sprache
English
First published in
Number in series
288
Article Number
41
Citation
32nd EACSL Annual Conference on Computer Science Logic, CSL 2024
Contribution to Conference
Publisher DOI
Scopus ID
Publisher
Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH
ISBN
978-3-95977-310-2
Two particularly active branches of research in constraint satisfaction are the study of promise constraint satisfaction problems (PCSPs) with finite templates and the study of infinite-domain constraint satisfaction problems with ω-categorical templates. In this paper, we explore some connections between these two hitherto unrelated fields and describe a general approach to studying the complexity of PCSPs by constructing suitable infinite CSP templates. As a result, we obtain new characterizations of the power of various classes of algorithms for PCSPs, such as first-order logic, arc consistency reductions, and obtain new proofs of the characterizations of the power of the classical linear and affine relaxations for PCSPs.
Subjects
first-order logic
homogeneous structures
polymorphisms
promise constraint satisfaction problems
DDC Class
004: Computer Sciences
510: Mathematics