License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ICALP.2019.57
URN: urn:nbn:de:0030-drops-106339
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2019/10633/
Ficak, Miron ;
Kozik, Marcin ;
Olsák, Miroslav ;
Stankiewicz, Szymon
Dichotomy for Symmetric Boolean PCSPs
Abstract
In one of the most actively studied version of Constraint Satisfaction Problem, a CSP is defined by a relational structure called a template. In the decision version of the problem the goal is to determine whether a structure given on input admits a homomorphism into this template. Two recent independent results of Bulatov [FOCS'17] and Zhuk [FOCS'17] state that each finite template defines CSP which is tractable or NP-complete.
In a recent paper Brakensiek and Guruswami [SODA'18] proposed an extension of the CSP framework. This extension, called Promise Constraint Satisfaction Problem, includes many naturally occurring computational questions, e.g. approximate coloring, that cannot be cast as CSPs. A PCSP is a combination of two CSPs defined by two similar templates; the computational question is to distinguish a YES instance of the first one from a NO instance of the second.
The computational complexity of many PCSPs remains unknown. Even the case of Boolean templates (solved for CSP by Schaefer [STOC'78]) remains wide open. The main result of Brakensiek and Guruswami [SODA'18] shows that Boolean PCSPs exhibit a dichotomy (PTIME vs. NPC) when "all the clauses are symmetric and allow for negation of variables". In this paper we remove the "allow for negation of variables" assumption from the theorem. The "symmetric" assumption means that changing the order of variables in a constraint does not change its satisfiability. The "negation of variables" means that both of the templates share a relation which can be used to effectively negate Boolean variables.
The main result of this paper establishes dichotomy for all the symmetric boolean templates. The tractability case of our theorem and the theorem of Brakensiek and Guruswami are almost identical. The main difference, and the main contribution of this work, is the new reason for hardness and the reasoning proving the split.
BibTeX - Entry
@InProceedings{ficak_et_al:LIPIcs:2019:10633,
author = {Miron Ficak and Marcin Kozik and Miroslav Ols{\'a}k and Szymon Stankiewicz},
title = {{Dichotomy for Symmetric Boolean PCSPs}},
booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)},
pages = {57:1--57:12},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-109-2},
ISSN = {1868-8969},
year = {2019},
volume = {132},
editor = {Christel Baier and Ioannis Chatzigiannakis and Paola Flocchini and Stefano Leonardi},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10633},
URN = {urn:nbn:de:0030-drops-106339},
doi = {10.4230/LIPIcs.ICALP.2019.57},
annote = {Keywords: promise constraint satisfaction problem, PCSP, algebraic approach}
}
|
Keywords: |
|
promise constraint satisfaction problem, PCSP, algebraic approach |
|
Collection: |
|
46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) |
|
Issue Date: |
|
2019 |
|
Date of publication: |
|
04.07.2019 |
