#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region

被引：26

作者：

Cai, Jin-Yi ^{[1
]}

Galanis, Andreas ^{[2
]}

Goldberg, Leslie Ann ^{[2
]}

Guo, Heng ^{[1
]}

Jerrum, Mark ^{[3
]}

Stefankovic, Daniel ^{[4
]}

Vigoda, Eric ^{[5
]}

机构：

[1] Univ Wisconsin, Dept Comp Sci, 1210 W Dayton St, Madison, WI 53706 USA

[2] Univ Oxford, Dept Comp Sci, Wolfson Bldg,Pk Rd, Oxford OX1 3QD, England

[3] Univ London, Sch Math Sci, Queen Mary, Mile End Rd, London E1 4NS, England

[4] Univ Rochester, Dept Comp Sci, Rochester, NY 14627 USA

[5] Georgia Inst Technol, Sch Comp Sci, Atlanta, GA 30332 USA

来源：

JOURNAL OF COMPUTER AND SYSTEM SCIENCES | 2016年 / 82卷 / 05期

基金：

美国国家科学基金会; 欧洲研究理事会;

关键词：

Spin systems; Approximate counting; Complexity; #BIS-hardness; Phase transition; COMPLEXITY;

D O I：

10.1016/j.jcss.2015.11.009

中图分类号：

TP3 [计算技术、计算机技术];

学科分类号：

0812 ;

摘要：

Counting independent sets on bipartite graphs (#BIS) is considered a canonical counting problem of intermediate approximation complexity. It is conjectured that #BIS neither has an FPRAS nor is as hard as #SAT to approximate. We study #BIS in the general framework of two-state spin systems on bipartite graphs. We define two notions, nearly-independent phase-correlated spins and unary symmetry breaking. We prove that it is #BIS-hard to approximate the partition function of any 2-spin system on bipartite graphs supporting these two notions. Consequently, we classify the complexity of approximating the partition function of antiferromagnetic 2-spin systems on bounded-degree bipartite graphs. (C) 2015 Elsevier Inc. All rights reserved.

引用

页码：690 / 711

页数：22