Tractability in constraint satisfaction problems: a survey

被引：33
作者：
Carbonnel, Clement [1 ,2 ]
Cooper, Martin C. [3 ]
机构：
[1] CNRS, LAAS, 7 Ave Colonel Roche, F-31400 Toulouse, France
[2] Univ Toulouse, INP Toulouse, LAAS, F-31400 Toulouse, France
[3] Univ Toulouse 3, IRIT, F-31062 Toulouse, France
来源：
CONSTRAINTS | 2016年 / 21卷 / 02期
基金：
英国工程与自然科学研究理事会;
关键词：
Computational complexity; Polynomial-time; Dichotomy; Tractable language; Polymorphism; Microstructure; Forbidden pattern; Relaxation; FIXED-PARAMETER TRACTABILITY; COMBINATORIAL PROBLEMS; COMPLEXITY; DICHOTOMY; CONSISTENCY; ALGORITHM; CSP; EXPRESSIBILITY; SATISFIABILITY; COMPLETENESS;
D O I：
10.1007/s10601-015-9198-6
中图分类号：
TP18 [人工智能理论];
学科分类号：
081104 ; 0812 ; 0835 ; 1405 ;
摘要：
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.
引用
收藏
页码：115 / 144
页数：30
相关论文
共 160 条
[1]   FIXED-PARAMETER TRACTABILITY AND COMPLETENESS .4. ON COMPLETENESS FOR W[P] AND PSPACE ANALOGS [J].
ABRAHAMSON, KA ;
DOWNEY, RG ;
FELLOWS, MR .
ANNALS OF PURE AND APPLIED LOGIC, 1995, 73 (03) :235-276
[2]   Hypertree width and related hypergraph invariants [J].
Adler, Isolde ;
Gottlob, Georg ;
Grohe, Martin .
EUROPEAN JOURNAL OF COMBINATORICS, 2007, 28 (08) :2167-2181
[3]   MAINTAINING KNOWLEDGE ABOUT TEMPORAL INTERVALS [J].
ALLEN, JF .
COMMUNICATIONS OF THE ACM, 1983, 26 (11) :832-843
[4]  
[Anonymous], 1990, Handbook of Theoretical Computer Science, Volume B: Formal Models and Semantics
[5]  
[Anonymous], 1979, Computers and Intractablity: A Guide to the Theory of NP-Completeness
[6]  
ARNBORG S, 1985, BIT, V25, P2, DOI 10.1007/BF01934985
[7]   COMPLEXITY OF FINDING EMBEDDINGS IN A K-TREE [J].
ARNBORG, S ;
CORNEIL, DG ;
PROSKUROWSKI, A .
SIAM JOURNAL ON ALGEBRAIC AND DISCRETE METHODS, 1987, 8 (02) :277-284
[8]  
Barto L., 2011, CANADIAN J MATH
[9]   The collapse of the bounded width hierarchy [J].
Barto, Libor .
JOURNAL OF LOGIC AND COMPUTATION, 2016, 26 (03) :923-943
[10]   Constraint Satisfaction Problems Solvable by Local Consistency Methods [J].
Barto, Libor ;
Kozik, Marcin .
JOURNAL OF THE ACM, 2014, 61 (01)
12345678910