Conference item
Beyond PCSP(1-in-3,NAE)
- Abstract:
-
The promise constraint satisfaction problem (PCSP) is a recently introduced vast generalisation of the constraint satisfaction problem (CSP) that captures approximability of satisfiable instances. A PCSP instance comes with two forms of each constraint: a strict one and a weak one. Given the promise that a solution exists using the strict constraints, the task is to find a solution using the weak constraints. While there are by now several dichotomy results for fragments of PCSPs, they all consider (in some way) symmetric PCSPs.
1-in-3-SAT and Not-All-Equal-3-SAT are classic examples of Boolean symmetric (non-promise) CSPs. While both problems are NP-hard, Brakensiek and Guruswami showed [SODA'18] that given a satisfiable instance of 1-in-3-SAT one can find a solution to the corresponding instance of (weaker) Not-All-Equal-3-SAT. In other words, the PCSP template (𝟏-in-𝟑,NAE) is tractable.
We focus on non-symmetric PCSPs. In particular, we study PCSP templates obtained from the Boolean template (𝐭-in-𝐤, NAE) by either adding tuples to 𝐭-in-𝐤 or removing tuples from NAE. For the former, we classify all templates as either tractable or not solvable by the currently strongest known algorithm for PCSPs, the combined basic LP and affine IP relaxation of Brakensiek and Guruswami [SODA'20]. For the latter, we classify all templates as either tractable or NP-hard.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Version of record, 834.4KB, Terms of use)
-
- Publisher copy:
- 10.4230/LIPIcs.ICALP.2021.121
Authors
- Publisher:
- Schloss Dagstuhl - Leibniz-Zentrum für Informatik
- Pages:
- 121:1–121:14
- Series:
- Leibniz International Proceedings in Informatics
- Series number:
- 198
- Place of publication:
- Germany
- Publication date:
- 2021-07-02
- Acceptance date:
- 2021-04-22
- Event title:
- 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)
- Event location:
- Online (Glasgow, Scotland)
- Event website:
- http://easyconferences.eu/icalp2021/
- Event start date:
- 2021-07-12
- Event end date:
- 2021-07-16
- DOI:
- ISSN:
-
1868-8969
- ISBN:
- 9783959771955
- Language:
-
English
- Keywords:
- Pubs id:
-
1173839
- Local pid:
-
pubs:1173839
- Deposit date:
-
2021-04-26
Terms of use
- Copyright holder:
- Brandts and Živný
- Copyright date:
- 2021
- Rights statement:
- © Alex Brandts and Stanislav Živný; licensed under Creative Commons License CC-BY 4.0
- Notes:
- This paper was presented at the 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021), 12-16 July 2021, Online (Glasgow, Scotland).
If you are the owner of this record, you can report an update to it here: Report update to this record