Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey
Fine-Grained Complexity of Constraint Satisfaction Problems through Partial Polymorphisms: A Survey
复制标题
通过部分多态性约束满足问题的细粒度复杂性：一项调查
DOI：
--
复制
发表时间：
2019
期刊：
影响因子：
--
通讯作者：
Victor Lagerkvist
中科院分区：
文献类型：
--
作者：
Miguel Couceiro;L. Haddad;Victor Lagerkvist
约束满足问题是与通用代数和克隆理论密切相关的组合问题。最近证明的CSP二分定理表明有限域CSP总是可处理的或np完全的。然而，在棘手的情况下，有一个看似很大的差异在复杂性，这是不能解释的经典代数方法使用多态性。在这篇文章中，我们将研究一种基于部分多态性的替代方法，这对于研究np完全csp的细粒度复杂性很有用。此外，我们将阐述一些具有挑战性的开放性问题的研究领域。
Constraint satisfaction problems (CSPs) are combinatorial problems with strong ties to universal algebra and clone theory. The recently proved CSP dichotomy theorem states that finite-domain CSPs are always either tractable or NP-complete. However, among the intractable cases there is a seemingly large variance in complexity, which cannot be explained by the classical algebraic approach using polymorphisms. In this contribution we will survey an alternative approach based on partial polymorphisms, which is useful for studying the fine-grained complexity of NP-complete CSPs. Moreover, we will state some challenging open problems in the research field.