Symbolic Integration and the Complexity of Computing Averages
Symbolic Integration and the Complexity of Computing Averages
复制标题
符号积分和计算平均值的复杂性
DOI：
10.1109/focs.2015.79
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Srivastava
中科院分区：
文献类型：
--
作者：
L. Schulman;A. Sinclair;P. Srivastava
我们研究了统计物理和组合数学中出现的几个自然问题的计算复杂性。特别是，我们考虑以下问题：伊辛模型（铁磁和反铁磁设置）的平均磁化强度和平均能量，在硬核模型中的一个独立集的平均大小，以及在单体-二聚体模型中匹配的平均大小。我们证明，对于所有的非平凡值的基础模型参数，精确计算这些平均值是P-困难的。与Sinclair和Srivastava（2013）关于铁磁Ising模型的平均磁化强度的先前结果相比，我们的方法没有使用任何关于配分函数的复零点的Lee-Yang型定理。事实上，这是由于缺乏合适的李-杨定理的模型，如反铁磁伊辛模型，我们在这里研究的一些问题是由辛克莱和斯利瓦斯塔瓦开放。在本文中，我们使用自动符号积分理论中一些相对简单和众所周知的想法来完成我们的硬度约简。
We study the computational complexity of several natural problems arising in statistical physics and combinatorics. In particular, we consider the following problems: the mean magnetization and mean energy of the Ising model (both the ferromagnetic and the anti-ferromagnetic settings), the average size of an independent set in the hard core model, and the average size of a matching in the monomer-dimer model. We prove that for all non-trivial values of the underlying model parameters, exactly computing these averages is #P-hard. In contrast to previous results of Sinclair and Srivastava (2013) for the mean magnetization of the ferromagnetic Ising model, our approach does not use any Lee-Yang type theorems about the complex zeros of partition functions. Indeed, it was due to the lack of suitable Lee-Yang theorems for models such as the anti-ferromagnetic Ising model that some of the problems we study here were left open by Sinclair and Srivastava. In this paper, we instead use some relatively simple and well-known ideas from the theory of automatic symbolic integration to complete our hardness reductions.