Algebraic approach to promise constraint satisfaction
Algebraic approach to promise constraint satisfaction
复制标题
承诺约束满足的代数方法
DOI：
10.1145/3313276.3316300
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Bulín J
中科院分区：
文献类型：
--
作者：
Bulín J
约束满足问题(CSP)的复杂性和可逼近性在过去的20年里得到了广泛的研究。最近提出了CSP的一个新版本，Promise CSP(PCSP)，其动机是关于可满足性和图着色变量的可逼近性的公开问题。PCSP大大扩展了标准决策CSP。在代数方法的指导下，最近对有限域上具有完全固定约束语言的CSP的复杂性进行了完全分类，该方法使用多态-解空间的高维对称-来分析问题的复杂性。PCSP的相应分类是开放的，并包含了一些长期未解决的问题，如近似图着色的复杂性，作为特例.基本的代数方法是由Brakensek和Guruswami提出的，在本文中，我们对其进行了显著的扩展，并将其从多态的具体性质提升到其抽象性质.我们引入了一类新的问题，它们可以看作(Gap)标签覆盖问题的代数版本，并证明了每个具有固定约束语言的PCSP等价于这种形式的问题。这使我们能够确定一种非常适合于通过代数方法比较和关联不同PCSP的复杂性的更好的“对称性度量”。我们通过给出一般的和特定的硬度/可控性结果来演示我们的理论是如何应用的。在其他方面，我们改进了近似图染色的最新技术，证明了对于任一≥3，很难找到给定k-可染图的1(2k-1)-着色。
The complexity and approximability of the constraint satisfaction problem (CSP) has been actively studied over the past 20 years. A new version of the CSP, the promise CSP (PCSP), has recently been proposed, motivated by open questions about the approximability of variants of satisfiability and graph colouring. The PCSP significantly extends the standard decision CSP. The complexity of CSPs with a fixed constraint language on a finite domain has recently been fully classified, greatly guided by the algebraic approach, which uses polymorphisms—high-dimensional symmetries of solution spaces—to analyse the complexity of problems. The corresponding classification for PCSPs is wide open and includes some long-standing open questions, such as the complexity of approximate graph colouring, as special cases.The basic algebraic approach to PCSP was initiated by Brakensiek and Guruswami, and in this article, we significantly extend it and lift it from concrete properties of polymorphisms to their abstract properties. We introduce a new class of problems that can be viewed as algebraic versions of the (Gap) Label Cover problem and show that every PCSP with a fixed constraint language is equivalent to a problem of this form. This allows us to identify a “measure of symmetry” that is well suited for comparing and relating the complexity of different PCSPs via the algebraic approach. We demonstrate how our theory can be applied by giving both general and specific hardness/tractability results. Among other things, we improve the state-of-the-art in approximate graph colouring by showing that, for anyk≥ 3, it is NP-hard to find a (2k-1)-colouring of a givenk-colourable graph.
登录
查看更多内容
无限域约束满足问题的两个二分猜想的等价性
DOI：
--
发表时间：
2017
期刊：
Logic in Computer Science
影响因子：
--
作者：
L. Barto;M. Kompatscher;M. Olsák;Trung Van Pham;M. Pinsker
通讯作者：
M. Pinsker
约束满足问题：复杂性和近似性（Dagstuhl 研讨会 18231）
DOI：
--
发表时间：
2018
期刊：
Dagstuhl Reports
影响因子：
--
作者：
Martin Grohe;V. Guruswami;Stanislav Živný
通讯作者：
Stanislav Živný
三色 H 可色图的复杂性
DOI：
--
发表时间：
2019
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
A. Krokhin;Jakub Opršal
通讯作者：
Jakub Opršal
DOI：
10.1145/2528400
发表时间：
2008-07
期刊：
Electron. Colloquium Comput. Complex.
影响因子：
--
作者：
A. Bulatov
通讯作者：
A. Bulatov
闭包函数和宽度 1 问题
DOI：
--
发表时间：
1999
期刊：
International Conference on Principles and Practice of Constraint Programming
影响因子：
--
作者：
V. Dalmau;J. Pearson
通讯作者：
J. Pearson