Tractability in constraint satisfaction problems: a survey
Tractability in constraint satisfaction problems: a survey
复制标题
DOI：
10.1007/s10601-015-9198-6
复制
发表时间：
2015-07
期刊：
影响因子：
1.6
通讯作者：
Clément Carbonnel;Martin C. Cooper
中科院分区：
文献类型：
--
作者：
Clément Carbonnel;Martin C. Cooper
尽管约束满足问题(CSP)是NP完全的，但许多容易处理的CSP实例已经被识别出来。在讨论了易操纵性的不同形式和用途之后，我们描述了一些具有里程碑意义的易操纵性类，并综述了最近的理论结果。虽然我们专注于经典的CSP，但我们也讨论了它对无限区域和优化的重要扩展，以及#CSP和QCSP。
Even though the Constraint Satisfaction Problem (CSP) is NP-complete, many tractable classes of CSP instances have been identified. After discussing different forms and uses of tractability, we describe some landmark tractable classes and survey recent theoretical results. Although we concentrate on the classical CSP, we also cover its important extensions to infinite domains and optimisation, as well as #CSP and QCSP.