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 [SICOP'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 PCSP template (1-in-3,NAE) is tractable. 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 the currently strongest known algorithm for PCSPs, the combined basic LP and affine IP relaxation of Brakensiek, Guruswami, Wrochna, and Zivny [SICOMP'20]. For the latter, we classify all templates as either tractable or NP-hard.
翻译:承诺限制满意度问题( PCSP) 是最近对制约满意度问题( PCSP) 的广泛概括化, 它捕捉到可讽刺的事例。 PCSP 实例包含两种不同的制约形式: 严格和弱。 鉴于有希望使用严格的制约来找到解决办法, 任务在于利用薄弱的制约来找到解决办法。 虽然现在对PCSP的碎片有几种分解结果, 它们都认为( 某种方式) 对称 PCSP 。 1 - in-3- SAT 和 Not- All- Equal-3- SAT 是 Boolean 的典型例子。 PCSP 典型的( 非承诺- ) CSP 。 虽然这两个问题都是 NP- hard, Braksenseek 和 Guruswami 都显示了[SI'21], 但考虑到 1- in-3 SAT 的可争议性实例, 它们都认为( weker- Al- Equal-3- SAT 的对应例子。 PCSP 模板(1- In- NA E) 是典型的, 我们所了解的。