Beyond PCSP(1-in-3,NAE)

1-in-3-SAT and Not-All-Equal-3-SAT are classic examples of Boolean symmetric (non-promise) constraint satisfaction problems (CSPs). While both problems are NP-hard, Brakensiek and Guruswami showed [SICOMP'21] 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 promise CSP template ( 1 -in- 3, NAE ) is tractable. Unlike previously established dichotomy results for fragments of promise CSPs (PCSPs), we focus on non-symmetric PCSPs. In particular, we study PCSP templates obtained from the Boolean template ( t -in- k, NAE ) by either adding tuples to t -in- k or removing tuples from NAE. For the former, we classify all templates as either tractable or not solvable by one of the strongest known algorithm for PCSPs, the combined basic LP and affine IP relaxation of Brakensiek, Guruswami, Wrochna, and Živný [SICOMP'20]. For the latter, we classify all templates as either tractable or NP-hard.

Authors

• Alex Brandts
• Stanislav Živný

Keywords

No keywords are indexed for this paper.