计数问题的近似算法

摘要

按照计算复杂性对计数问题进行分类是理论计算机科学中的一个核心主题。尽管最近几年精确计数领域有很大的进展，对于计数问题的可近似性的研究却一直都很初步，我们仅仅在一些非常局限的模型内，才对计数问题的可近似性才有完整的刻画。
　　在这篇论文中，我们在Holant问题的框架中研究近似计数问题。这是一个简洁但是却有很强表达能力的计数问题框架，许多其它被充分研究过的问题框架，比如同态计数、计数CSP等，都可以看成它的特例。这篇论文是第一次在近似计数的场合系统的对Holant问题进行研究。具体来说，我们设计和发展了设计Holant问题近似算法的技术。我们涉及的技术可以分成两类。
　　马尔科夫链蒙特卡洛设计近似计数与取样算法的一个经典方法是马尔科夫链蒙特卡洛（Markov chain Monte Carlo，MCMC）方法。这个方法的关键是分析一个指定的马尔科夫链的收敛时间。我们给出了Holant问题上马尔科夫链收敛的一个新的刻画。这个刻画可以用来解释几乎所有之前在这个框架内成功的例子。并且，它能够被用来给出一些新的近似计数算法，包括b-匹配计数、b-边覆盖计数等组合问题。
　　相关性衰减另外一个相对更新的技术是所谓的相关性衰减方法。这个方法在最近被用来给出了反铁磁性二状态自旋系统的最优确定性近似计数算法，在这个问题上，基于MCMC方法目前并不能给出最优的算法。我们在Holant问题上使用这个方法，得到了一系列新的结果。
　　我们首先研究加权边覆盖计数问题。这是一个已经被充分研究了的组合问题，它可以在Holant问题框架内用非常简单的约束函数进行描述。在这之前，最好的基于MCMC方法的随机近似算法只能被应用在最大度不超过3的无权图上。我们成功的使用相关性衰减方法设计了一个确定性的近似算法，并且对于任何图与任意边权都适用。
　　我们接着考虑超图上的Hardcore模型。这个模型在统计物理中得到了广泛的研究，它推广了独立集计数问题，也等价于计算加权后单调合取范式的解的个数。在一般图上，这个模型的配分函数的近似性已经被完全的解决了。我们把这个结果推广到了超图上，并证明在可近似性的意义下，一般图实际上是最坏情况。
　　在精确计数的场合，无权斐波那契门是一类有核心地位的Holant问题，它可以被看成是很多其它Holant问题的计算元语。在有权的情况下，这个问题变成#P-难的了，因此，我们研究其可近似性。我们给不同参数范围内的问题设计了近似算法。类似于精确计数的场合，这些近似算法都可以通过全息变换转变成其它问题的近似算法。一个重要的例子就是计算铁磁性二状态自旋系统的配分函数。我们的结果是这个问题第一个确定的近似算法。
　　除此之外，我们还研究了在特殊图上的计数问题。
　　树状图我们考虑具有低树宽的图，这是一类很接近于树的图。这个概念在著名的图子式理论的发展过程中起到了很重要的作用。我们找出了一类可以在这类图上被高效解决的Holant问题。我们的算法推广了许多之前与树宽有关的精确计数算法。
　　平面图我们在平面图上设计了确定性的近似计数算法。我们的算法用到了平面图局部似树以及相关性衰减的性质。为了利用这两个性质，我们分别使用了我们给出的在树状图上的精确计数算法，以及最近提出的递归耦合技术。我们的结果可以看成是一个Holant问题在平面图上具有确定性近似算法的充分条件。
　　随机图我们考虑的另外一类特殊图是Erd?s-Rényi随机图G(n,p)。这类图具有较小的平均度以及很大的最大度。我们考虑在G(n,d/n)上计算合法q-着色问题。在问题参数满足q>3d+4时，我们设计了一个高效的取样器（等价于一个近似计数算法），这改进了之前最好的q>5.5d的结果。实际上，我们的算法对于更一般的模型和稀疏图类也成立。

目录

第一部分背景知识

第一章 论文概览

1.1 研究背景

1.2 本文贡献与章节安排

第二章 基本记号

2.1 集合与图论记号

2.2 函数

第三章 计算复杂性

第四章 计数问题框架

4.1 自旋系统

4.2 Holant问题

第五章 结构图论

5.1 子式

5.2 树分解

第二部分相关性衰减技术

第六章 加权边覆盖计数问题

6.1 悬边

6.2 近似边缘概率

6.3 相关性衰减分析

6.4 主引理的证明

6.5 本章小结

第七章 加权单调CNF计数

7.1 绪论

7.2 边缘概率递推式

7.3 计算边缘概率算法

7.4 相关性衰减分析

7.5 本章小结

第八章 加权斐波那契门

8.1 绪论

8.2 斐波那契门的递推式

8.3 算法

8.4 边缘概率的上下界

8.5 相关性衰减分析

8.6 全息变换与二状态自旋系统

8.7 本章小结

第三部分特殊结构上的近似计数

第九章 树宽与计数问题

9.1 非对称函数

9.2 规范函数

9.3 割分解

9.4 规范函数的结构

9.5 计数算法

9.6 相关性衰减

9.7 本章小结

第十章 随机图

10.1 绪论

10.2 预备知识

10.3 基于块的计算树

10.4 相关性衰减

10.5 FPTAS与取样算法

10.6 随机图

10.7 本章小结

第四部分基于马尔科夫链蒙特卡洛方法的近似计数

第十一章 可缠绕性和近似计数

11.1 绪论

11.2 马尔科夫链

11.3 可缠绕性的刻画

11.4 b-边覆盖计数

11.5 b-匹配问题计数

11.6 加权b-边覆盖与b-匹配

11.7 不可缠绕的函数

11.8 本章小结

附录A 第八章的证明

A.1 定理8.1的证明

A.2 定理8.2的证明

A.3 定理8.3的证明

附录B 第九章的证明

B.1 定理9.6的证明

参考文献

致谢

攻读学位期间发表的学术论文