Technical Perspective Constraint Satisfaction Problems and Computational Complexity

被引：0

作者：

Jerrum, Mark ^{[1
]}

机构：

[1] Univ London, London WC1E 7HU, England

来源：

COMMUNICATIONS OF THE ACM | 2010年 / 53卷 / 09期

关键词：

D O I：

10.1145/1810891.1810913

中图分类号：

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

学科分类号：

0812 ;

摘要：

引用

页码：98 / 98

页数：1

共 50 条

[31] A DICHOTOMY THEOREM FOR THE RESOLUTION COMPLEXITY OF RANDOM CONSTRAINT SATISFACTION PROBLEMS
Chan, Siu On
Molloy, Michael
SIAM JOURNAL ON COMPUTING, 2013, 42 (01) : 27 - 60
[32] Phase transitions and computational difficulty in random constraint satisfaction problems
Krzakala, Florent
Zdeborova, Lenka
INTERNATIONAL WORKSHOP ON STATISTICAL-MECHANICAL INFORMATICS 2007 (IW-SMI 2007), 2008, 95
[33] Improving the computational efficiency in symmetrical numeric constraint satisfaction problems
Gasca, R. M.
Del Valle, C.
Cejudo, V.
Barba, I.
CURRENT TOPICS IN ARTIFICIAL INTELLIGENCE, 2006, 4177 : 269 - 279
[34] Computational complexity of multi-way, dataflow constraint problems
Trombettoni, G
Neveu, B
IJCAI-97 - PROCEEDINGS OF THE FIFTEENTH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE, VOLS 1 AND 2, 1997, : 358 - 363
[35] Characterising the complexity of constraint satisfaction problems defined by 2-constraint forbidden patterns
Cooper, Martin C.
Escamocher, Guillaume
DISCRETE APPLIED MATHEMATICS, 2015, 184 : 89 - 113
[36] The complexity of homomorphism and constraint satisfaction problems seen from the other side
Grohe, Martin
JOURNAL OF THE ACM, 2007, 54 (01)
[37] Resolution complexity of random constraint satisfaction problems: Another half of the story
Gao, Y
Culberson, J
DISCRETE APPLIED MATHEMATICS, 2005, 153 (1-3) : 124 - 140
[38] The complexity of homomorphism and constraint satisfaction problems seen from the other side
Grohe, M
44TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, PROCEEDINGS, 2003, : 552 - 561
[39] THE COMPLEXITY OF SOME POLYNOMIAL NETWORK CONSISTENCY ALGORITHMS FOR CONSTRAINT SATISFACTION PROBLEMS
MACKWORTH, AK
FREUDER, EC
ARTIFICIAL INTELLIGENCE, 1985, 25 (01) : 65 - 74
[40] Boolean constraint satisfaction: complexity results for optimization problems with arbitrary weights
Jonsson, P
THEORETICAL COMPUTER SCIENCE, 2000, 244 (1-2) : 189 - 203

← 1 2 3 4 5 →