The Complexity of Counting in Constraint Satisfaction Problems

约束满足问题中计数的复杂性

• 批准号: EP/E064906/1
• 负责人: Mark Jerrum
• 金额: $ 13.56万
• 依托单位: Queen Mary University of London
• 依托单位国家: 英国
• 项目类别: Research Grant
• 财政年份: 2007
• 资助国家: 英国
• 起止时间: 2007 至 无数据
• 项目状态: 已结题
• 来源: https://gtr.ukri.org/projects?ref=EP%2FE064906%2F1
• 关键词: Complexity; Counting; Constraint; Satisfaction; Problems

Constraint Satisfaction, which originated in Artificial Intelligence, provides a general framework for modelling decision problems, and has many practical applications. Decisions are modelled by variables, which are subject to constraints, modelling logical and resource restrictions. The paradigm is sufficiently broad that many interesting problems can be modelled, from satisfiability problems to scheduling problems and graph-theory problems. Understanding the complexity of constraint satisfaction problems has become a major and active area within computational complexity. The overall goal is to classify CSPs according to complexity, giving a characterisation for which CSPs are tractable. We will focus especially on characterizing the complexity of counting in Constraint Satisfaction problems. Specifically, we will study the complexity of exactly counting CSP solutions, approximately counting CSP solutions, and sampling CSP solutions from appropriately-defined probability distributions. These important questions are closely related, and are strongly connected to questions in statistical physics.

约束满足理论起源于人工智能，它为决策问题的建模提供了一个通用的框架，并有许多实际应用。决策由变量建模，这些变量受到约束、建模逻辑和资源限制。该范式足够广泛，可以模拟许多有趣的问题，从可满足性问题到调度问题和图论问题。理解约束满足问题的复杂性已经成为计算复杂性的一个主要和活跃的领域。总体目标是根据复杂性对CSP进行分类，给出CSP易于处理的特征。我们将特别关注描述约束满足问题中计数的复杂性。具体来说，我们将研究精确计数CSP解决方案，近似计数CSP解决方案，并从适当定义的概率分布抽样CSP解决方案的复杂性。这些重要的问题是密切相关的，并且与统计物理学中的问题密切相关。

项目成果

The complexity of parity graph homomorphism: an initial investigation

奇偶图同态的复杂性：初步研究

• DOI: 10.48550/arxiv.1309.4033
• 发表时间: 2013
• 作者: Faben J

An approximation trichotomy for Boolean #CSP

布尔值的近似三分法

• DOI: 10.1016/j.jcss.2009.08.003
• 发表时间: 2010
• 期刊: Journal of Computer and System Sciences
• 影响因子: 1.1
• 作者: Dyer M

A Complexity Dichotomy for Partition Functions with Mixed Signs

混合符号配分函数的复杂度二分法

• DOI: 10.1137/090757496
• 发表时间: 2010
• 期刊: SIAM Journal on Computing
• 影响因子: 1.6
• 作者: Goldberg L

Approximating the partition function of the ferromagnetic Potts model

• DOI: 10.1145/2371656.2371660
• 发表时间: 2010-02
• 期刊: Algorithmica
• 影响因子: 1.1
• 作者: L. A. Goldberg;M. Jerrum

The mixing time of Glauber dynamics for coloring regular trees

普通树木着色的芒硝动力学混合时间

• DOI: 10.1002/rsa.20303
• 发表时间: 2010
• 期刊: Random Structures & Algorithms
• 影响因子: 1
• 作者: Goldberg L