The Complexity of Counting in 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.