Inapproximability After Uniqueness Phase Transition in Two-Spin Systems
Abstract
A two-state spin system is specified by a matrix
A =
A_{0,0} A_{0,1}
A_{1,0} A_{1,1}
= beta 1
1 gamma
where beta, gamma >= 0. Given an input graph G=(V,E), the partition function Z_A(G) of a system is defined as Z_A(G)=sum_{sigma: V --> {0, 1}} \prod_{(u,v) in E} A_{sigma(u), sigma(v)}.
We prove inapproximability results for the partition function in the region specified by the non-uniqueness condition from phase transition for the Gibbs measure. More specifically, assuming NP not= RP, for any fixed beta,gamma in the unit square, there is no randomized polynomial-time algorithm that approximates Z_A(G) for d-regular graphs G with relative error epsilon=10^{-4}, if d = Omega(Delta(beta,gamma)), where Delta(beta,gamma) > 1/(1- beta gamma) is the uniqueness threshold. Up to a constant factor, this hardness result confirms the conjecture that the uniqueness phase transition coincides with the transition from computational tractability to intractability for Z_A(G). We also show a matching inapproximability result for a region of parameters beta, gamma outside the unit square, and all our results generalize to partition functions with an external field.
Subject
Phase Transition
Uniqueness Condition
Complexity
Inapproximability
Spin Systems
Partition Function
Permanent Link
http://digital.library.wisc.edu/1793/61488Citation
TR1715