Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
Symmetric Promise Constraint Satisfaction Problems: Beyond the Boolean Case
复制标题
对称承诺约束满足问题：超越布尔情况
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Kevin M. Berg
中科院分区：
文献类型：
--
作者：
L. Barto;Diego Battistelli;Kevin M. Berg
承诺约束满足问题（Promise Constraint Satisfaction Problem，PCSP）是约束满足问题（Constraint Satisfaction Problem，CSP）的一个推广。我们调查的计算复杂性的一类PCSP超出了大多数研究的情况下，可满足性和图着色问题的近似变量。我们给出了一类PCSP的几乎完全分类的形式：给定一个3-一致超图，有一个容许的2-染色，找到一个容许的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."
DOI：
10.1145/3313276.3316300
发表时间：
2019
期刊：
--
影响因子：
--
作者：
Bulín J
通讯作者：
Bulín J
结合基本线性规划和仿射松弛来解决承诺约束满足问题的威力
影响因子：
1.6
作者：
Brakensiek, Joshua;Guruswami, Venkatesan;Wrochna, Marcin;Živný, Stanislav
通讯作者：
Živný, Stanislav