Constraint Satisfaction Problems Solvable by Local Consistency Methods

被引：113

作者：

Barto, Libor ^{[1
]}

Kozik, Marcin ^{[2
]}

机构：

[1] Charles Univ Prague, Fac Math & Phys, Dept Algebra, Prague 18675 8, Czech Republic

[2] Jagiellonian Univ, Theoret Comp Sci Dept, Fac Math & Comp Sci, PL-30348 Krakow, Poland

来源：

JOURNAL OF THE ACM | 2014年 / 61卷 / 01期

关键词：

Algorithms; Theory; Constraint satisfaction problem; local consistency checking; BOUNDED WIDTH;

D O I：

10.1145/2556646

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

We prove that constraint satisfaction problems without the ability to count are solvable by the local consistency checking algorithm. This settles three (equivalent) conjectures: Feder-Vardi [SICOMP'98], Bulatov [LICS'04] and Larose-Zadori [AU'07].

引用

页数：19

共 33 条

[1]

BARTO L, 2013, MALTSEV CONDIT UNPUB

[2]

BARTO L, 2013, COLLAPSE BOUND UNPUB

[3]

Barto L, 2012, STOC'12: PROCEEDINGS OF THE 2012 ACM SYMPOSIUM ON THEORY OF COMPUTING, P931

[4] 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

[5] 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

[6] CONGRUENCE DISTRIBUTIVITY IMPLIES BOUNDED WIDTH [J].

Barto, Libor ;

Kozik, Marcin .

SIAM JOURNAL ON COMPUTING, 2009, 39 (04) :1531-1542

[7]

Bergman C.H., 2011, Universal Algebra: Fundamentals and Selected Topics

[8]

Berman J, 2010, T AM MATH SOC, V362, P1445

[9] On the structure of abstract algebras [J].

Birkhoff, G .

PROCEEDINGS OF THE CAMBRIDGE PHILOSOPHICAL SOCIETY, 1935, 31 :433-454

[10]

Bodnarchuk VG., 1969, KIBERNETIKA KIEV, V5, P1

← 1 2 3 4 →