Promise Constraint Satisfaction Problenms (PCSPs) provide a powerful setting for treating the complexity of approximation. In a PCSP, we are given variables and constraints, where the constraints come in a strict and in a relaxed version; the goal is to distinguish instances that are satisfiable with the strict version of constraints from those which are not satisfiable even in the relaxed sense. A concrete PCSP, whose complexity is a notorious question in approximation, is the problem to distinguish 3-colorable graphs from those that are not even 10-colorable. We study methods from universal algebra and algebraic topology in order to classify the complexity of PCSPs.
Talks
Literature: L. Barto, J. Bulin, A. Krokhin, J. Oprsal, Algebraic approach to promise constraint satisfaction, Journal of the ACM 68/4 (2021), 1-66. https://arxiv.org/abs/1811.00970
[1811.00970] Algebraic approach to promise constraint satisfaction arxiv.org The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the last 20 years. A new version of the CSP, the promise CSP (PCSP) has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms --- high-dimensional symmetries of solution spaces --- to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases. The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this paper we significantly extend it and lift it from concrete properties of polymorphi
Continuous assessment.
Not necessary
Logik oder Algebra I
