Approximating the partition function of the ferromagnetic Potts model
Approximating the partition function of the ferromagnetic Potts model
复制标题
DOI：
10.1145/2371656.2371660
复制
发表时间：
2010-02
期刊：
影响因子：
1.1
通讯作者：
L. A. Goldberg;M. Jerrum
中科院分区：
文献类型：
--
作者：
L. A. Goldberg;M. Jerrum
我们提供的证据表明，当q >2时，计算上难以近似铁磁q态波茨模型的配分函数。具体来说，我们证明了复杂度类#RHPi在保持近似可约性下的配分函数是困难的。因此，近似配分函数就像近似求解各种计数问题一样困难，包括确定二部图中独立集的数量。我们的证明利用了“随机簇”模型的一阶相变，这是与q态波茨模型密切相关的图上的概率分布。
We provide evidence that it is computationally difficult to approximate the partition function of the ferromagnetic q-state Potts model when q > 2. Specifically, we show that the partition function is hard for the complexity class #RHPi under approximation-preserving reducibility. Thus, it is as hard to approximate the partition function as it is to find approximate solutions to a wide range of counting problems, including that of determining the number of independent sets in a bipartite graph. Our proof exploits the first-order phase transition of the “random cluster” model, which is a probability distribution on graphs that is closely related to the q-state Potts model.