Algorithms that count: exploring the limits of tractability

计算复杂性是对解决特定计算问题所需资源的严格研究。这些通常是决策问题（是否存在满足某些属性的结构？）或优化问题（什么是最优结构？），但在这个项目中，我们专注于第三类，即计数问题。这里的“计数问题”一词有广泛的解释；这类计算问题的例子包括：(i)“找到CNF布尔公式的满意赋值的个数”，（ii）“用加权图指定的相互作用评估Ising模型（统计物理中广泛研究的模型）的配分函数”，以及（iii）“找到凸体的体积”。例(i)是一个简单的计数问题，（ii）要求对自旋构型的加权和求值，（iii）是一个定积分，它是求和的极限情况。粗略地说，计算复杂度有两个目标，即下界和上界。建立一个下界等于证明，要达到一定的计算目标，需要一定的资源，比如时间或空间。一般来说，下界只能在一些复杂性理论假设下建立，最著名的是P不等于NP。在这个项目中，我们专注于建立上界的更乐观的活动，即为可证明只需要一定量资源的计算任务设计和分析算法。强调上限的部分理由是，近年来在下限方面取得了实质性进展，现在重要的是，看看这些在多大程度上可以与另一个方向相匹配。由于绝大多数计数问题是难以处理的，假设要寻找精确的解，就有必要研究各种逃脱路线：具有保证误差范围的有效近似算法，在有限类别的问题实例上证明有效的算法，以及参数化算法，其不良行为可以通过在实际问题实例中假设很小的参数来控制。拟议研究的另一个方面是缩小理论效率和实践效率之间的差距。在经典理论中，如果算法在实例大小上以时间多项式的形式运行，则认为算法是有效的。这种效率的理论概念在实践中通常与可追溯性相对应，但在计数问题的背景下，这种对应关系并不那么好，在计数问题中，马尔可夫链蒙特卡罗是最常见的解决技术。

Computational Complexity is the name given to the rigorous study of the resources required to solve specified computational problems. These are often decision problems (does there exist a structure satisfying certain properties?) or optimisation problems (what is the optimal structure?), but in this project we concentrate on a third class, namely counting problems. The phrase "counting problem" here is widely interpreted; examples of computational problems in this category include: (i) "find the number of satisfying assignments to a CNF Boolean formula", (ii) "evaluate the partition function of the Ising model (an extensively studied model in statistical physics) with interactions specified by a weighted graph", and (iii) "find the volume of a convex body". Example (i) is a straightforward counting problem, (ii) asks for the evaluation of a weighted sum over spin configurations, and (iii) is a definite integral, which is the limiting case of a summation. Crudely put, there are two objectives in computational complexity, namely lower bounds and upper bounds. Establishing a lower bound amounts to proving that a certain amount of resource, say, time or space, is required to achieve a certain computational goal. Generally, lower bounds can only be established under some complexity-theoretic assumption, the most famous being P not equal to NP. In this project we concentrate on the more optimistic activity of establishing upper bounds, i.e., designing and analysing algorithms for a computational task that provably require only a certain amount of resource. Part of the rationale for the stress on upper bounds is that substantial progress has been made in recent years on lower bounds, and it is important now to see how far these can be matched from the other direction. As the vast majority of counting problems are intractable, assuming exact solutions are sought, it will be necessary to investigate various escape routes: efficient approximation algorithms with guaranteed error bounds, algorithms that are provably efficient on restricted classes of problem instances, and parameterised algorithms whose bad behaviour can be controlled by a parameter that is assumed small in problem instances of practical interest. Another strand to the proposed research is to narrow the gap between what is efficient in theory and efficient in practice. In the classical theory, an algorithm is deemed to be efficient if it runs in time polynomial in the instance size. This theoretical notion of efficiency often corresponds to tractability in practice, but the correspondence is not so good in the context of counting problems, where Markov chain Monte Carlo is the most common solution technique.