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 条
  • [21] The resolution complexity of random constraint satisfaction problems
    Molloy, Michael
    Salavatipour, Mohammad R.
    SIAM JOURNAL ON COMPUTING, 2007, 37 (03) : 895 - 922
  • [22] The Complexity of Resilience Problems via Valued Constraint Satisfaction Problems
    Bodirsky, Manuel
    Semanisinova, Zaneta
    Lutz, Carsten
    PROCEEDINGS OF THE 39TH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE, LICS 2024, 2024,
  • [23] Experimental complexity analysis of continuous constraint satisfaction problems
    Shang, Y
    Fromherz, MPJ
    INFORMATION SCIENCES, 2003, 153 : 1 - 36
  • [24] The complexity of Boolean constraint satisfaction local search problems
    Chapdelaine, P
    Creignou, N
    ANNALS OF MATHEMATICS AND ARTIFICIAL INTELLIGENCE, 2005, 43 (1-4) : 51 - 63
  • [25] The complexity of Boolean constraint satisfaction local search problems
    Philippe Chapdelaine
    Nadia Creignou
    Annals of Mathematics and Artificial Intelligence, 2005, 43 : 51 - 63
  • [26] The complexity of constraint satisfaction problems for small relation algebras
    Cristani, M
    Hirsch, R
    ARTIFICIAL INTELLIGENCE, 2004, 156 (02) : 177 - 196
  • [27] Fine-Grained Time Complexity of Constraint Satisfaction Problems
    Jonsson, Peter
    Lagerkvist, Victor
    Roy, Biman
    ACM TRANSACTIONS ON COMPUTATION THEORY, 2021, 13 (01)
  • [28] The Complexity of Quantified Constraint Satisfaction Problems under Structural Restrictions
    Gottlob, Georg
    Greco, Gianluigi
    Scarcello, Francesco
    19TH INTERNATIONAL JOINT CONFERENCE ON ARTIFICIAL INTELLIGENCE (IJCAI-05), 2005, : 150 - 155
  • [29] A Dichotomy Theorem for the Resolution Complexity of Random Constraint Satisfaction Problems
    Chan, Siu On
    Molloy, Michael
    PROCEEDINGS OF THE 49TH ANNUAL IEEE SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE, 2008, : 634 - 643
  • [30] Turing Machines with Atoms, Constraint Satisfaction Problems, and Descriptive Complexity
    Klin, Bartek
    Lasota, Slawomir
    Ochremiak, Joanna
    Torunczyk, Szymon
    PROCEEDINGS OF THE JOINT MEETING OF THE TWENTY-THIRD EACSL ANNUAL CONFERENCE ON COMPUTER SCIENCE LOGIC (CSL) AND THE TWENTY-NINTH ANNUAL ACM/IEEE SYMPOSIUM ON LOGIC IN COMPUTER SCIENCE (LICS), 2014,
12345