The Dichotomy for Conservative Constraint Satisfaction Problems Revisited

被引：44
作者：
Barto, Libor [1 ]
机构：
[1] McMaster Univ, Dept Math & Stat, Hamilton, ON, Canada
来源：
26TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2011) | 2011年
关键词：
constraint satisfaction problem; list homomorphism problem; conservative algebra; dichotomy theorem; COMPLEXITY; THEOREM; GRAPHS;
D O I：
10.1109/LICS.2011.25
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
A central open question in the study of non-uniform constraint satisfaction problems (CSPs) is the dichotomy conjecture of Feder and Vardi stating that the CSP over a fixed constraint language is either NP-complete, or tractable. One of the main achievements in this direction is a result of Bulatov (LICS'03) confirming the dichotomy conjecture for conservative CSPs, that is, CSPs over constraint languages containing all unary relations. Unfortunately, the proof is very long and complicated, and therefore hard to understand even for a specialist. This paper provides a short and transparent proof.
引用
收藏
页码：301 / 310
页数：10
相关论文
共 26 条
[1]  
Barto L., CONSTRAINT SAT UNPUB
[2]  
Barto L., ABSORBING SUBA UNPUB
[3]   New conditions for Taylor varieties and CSP [J].
Barto, Libor ;
Kozik, Marcin .
25TH ANNUAL IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS 2010), 2010, :100-109
[4]   Constraint Satisfaction Problems of Bounded Width [J].
Barto, Libor ;
Kozik, Marcin .
2009 50TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE: FOCS 2009, PROCEEDINGS, 2009, :595-603
[5]   CONGRUENCE DISTRIBUTIVITY IMPLIES BOUNDED WIDTH [J].
Barto, Libor ;
Kozik, Marcin .
SIAM JOURNAL ON COMPUTING, 2009, 39 (04) :1531-1542
[6]   THE CSP DICHOTOMY HOLDS FOR DIGRAPHS WITH NO SOURCES AND NO SINKS (A POSITIVE ANSWER TO A CONJECTURE OF BANG-JENSEN AND HELL) [J].
Barto, Libor ;
Kozik, Marcin ;
Niven, Todd .
SIAM JOURNAL ON COMPUTING, 2009, 38 (05) :1782-1802
[7]  
Barto L, 2008, ACM S THEORY COMPUT, P789
[8]   Classifying the complexity of constraints using finite algebras [J].
Bulatov, A ;
Jeavons, P ;
Krokhin, A .
SIAM JOURNAL ON COMPUTING, 2005, 34 (03) :720-742
[9]  
BULATOV A, 2002, PRGRR0205 U OXF COMP
[10]   A dichotomy theorem for constraint satisfaction problems on a 3-element set [J].
Bulatov, AA .
JOURNAL OF THE ACM, 2006, 53 (01) :66-120
123