论文部分内容阅读
按照计算复杂性对计数问题进行分类是理论计算机科学中的一个核心主题。尽管最近几年精确计数领域有很大的进展，对于计数问题的可近似性的研究却一直都很初步，我们仅仅在一些非常局限的模型内，才对计数问题的可近似性才有完整的刻画。 在这篇论文中，我们在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的结果。实际上，我们的算法对于更一般的模型和稀疏图类也成立。