کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
10332686 | 687746 | 2016 | 22 صفحه PDF | دانلود رایگان |
عنوان انگلیسی مقاله ISI
#BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region
دانلود مقاله + سفارش ترجمه
دانلود مقاله ISI انگلیسی
رایگان برای ایرانیان
کلمات کلیدی
موضوعات مرتبط
مهندسی و علوم پایه
مهندسی کامپیوتر
نظریه محاسباتی و ریاضیات
پیش نمایش صفحه اول مقاله
![عکس صفحه اول مقاله: #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region #BIS-hardness for 2-spin systems on bipartite bounded degree graphs in the tree non-uniqueness region](/preview/png/10332686.png)
چکیده انگلیسی
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.
ناشر
Database: Elsevier - ScienceDirect (ساینس دایرکت)
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 690-711
Journal: Journal of Computer and System Sciences - Volume 82, Issue 5, August 2016, Pages 690-711
نویسندگان
Jin-Yi Cai, Andreas Galanis, Leslie Ann Goldberg, Heng Guo, Mark Jerrum, Daniel Å tefankoviÄ, Eric Vigoda,