论文标题
对称的承诺约束满意度问题：超越布尔案
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
论文作者
论文摘要
承诺约束满意度问题（PCSP）是最近对约束满意度问题（CSP）的广泛概括。我们研究了一类PCSP的计算复杂性，超出了研究最多的情况 - 令人满意的和图形问题的近似变体。我们为形式的PCSP类别提供了几乎完整的分类：给定具有可允许的2色的3-均匀的超图，找到可允许的3色，在该颜色下，通过三元对称关系给出了可接受性。这项工作中复杂性打开的唯一这种PCSP是自然的超图着色问题，在这种关系中，关系可以通过“如果两种颜色相等，那么剩下的一种是更高的”。
The Promise Constraint Satisfaction Problem (PCSP) is a recently introduced vast generalization of the Constraint Satisfaction Problem (CSP). We investigate the computational complexity of a class of PCSPs beyond the most studied cases - approximation variants of satisfiability and graph coloring problems. We give an almost complete classification for the class of PCSPs of the form: given a 3-uniform hypergraph that has an admissible 2-coloring, find an admissible 3-coloring, where admissibility is given by a ternary symmetric relation. The only PCSP of this sort whose complexity is left open in this work is a natural hypergraph coloring problem, where admissibility is given by the relation "if two colors are equal, then the remaining one is higher."
