论文标题
有限的（IN）可处理的承诺约束满意度问题
Finitely (In)tractable Promise Constraint Satisfaction Problems
论文作者
论文摘要
承诺约束满意度问题（PCSP）是约束满意度问题（CSP）的概括，其中包括满意度和图形着色问题的近似变体。 BARTO [LICS '19]表明，特定的PCSP是找到有效的不等3-SAT实例的有效解决方案的问题，这不是有限处理的，因为它可以通过可拖动的CSP琐碎的降低来解决，但是除非无限型csp在无限域（除非p = np = np）。我们通过为有限的障碍性和表征一类模板中的有限障碍的一般必要条件来开始对该现象的系统研究 - 对称布尔PCSPS的二分法定理中的“基本”可易处理病例，允许Brakensiek和Guruswami [Sodaoda'18]对对称的布尔PCSPS进行否定。
The Promise Constraint Satisfaction Problem (PCSP) is a generalization of the Constraint Satisfaction Problem (CSP) that includes approximation variants of satisfiability and graph coloring problems. Barto [LICS '19] has shown that a specific PCSP, the problem to find a valid Not-All-Equal solution to a 1-in-3-SAT instance, is not finitely tractable in that it can be solved by a trivial reduction to a tractable CSP, but such a CSP is necessarily over an infinite domain (unless P=NP). We initiate a systematic study of this phenomenon by giving a general necessary condition for finite tractability and characterizing finite tractability within a class of templates - the "basic" tractable cases in the dichotomy theorem for symmetric Boolean PCSPs allowing negations by Brakensiek and Guruswami [SODA'18].
