文章基本信息

标题：The Complexity of Ferromagnetic Two-spin Systems with External Fields
本地全文：下载
作者：Jingcheng Liu ; Pinyan Lu ; Chihao Zhang 等
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2014
卷号：28
页码：843-856
DOI：10.4230/LIPIcs.APPROX-RANDOM.2014.843
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：We study the approximability of computing the partition function for ferromagnetic two-state spin systems. The remarkable algorithm by Jerrum and Sinclair showed that there is a fully polynomial-time randomized approximation scheme (FPRAS) for the special ferromagnetic Ising model with any given uniform external field. Later, Goldberg and Jerrum proved that it is #BIS-hard for Ising model if we allow inconsistent external fields on different nodes. In contrast to these two results, we prove that for any ferromagnetic two-state spin systems except the Ising model, there exists a threshold for external fields beyond which the problem is #BIS-hard, even if the external field is uniform.
关键词：Spin System; #BIS-hard; FPRAS