Spin systems on k-regular graphs with complex edge functions
Let k >= 1 be an integer and let h = [GRAPHICS] be a complex-valued symmetric function on domain {0, 1) (i.e., where h(0. 1) = h(1, 0)). We introduce a new technique, called a syzygy, and prove a dichotomy theorem for the following class of problems, specified by k and h: given an arbitrary k-regular graph G = (V, E), where the function h is attached to each edge, compute Z(G) = Sigma(sigma:V ->(0,1)) Pi({u, v}is an element of E 11) h(sigma(u), sigma (v)). Z(center dot) is known as the partition function of the spin system, also known as counting graph homomorphisms on domain size two, and is a special case of Holant problems. The dichotomy theorem gives a complete classification of the computational complexity of this problem, depending on k and h. The dependence on k and h is explicit. (c) 2012 Elsevier B.V. All rights reserved.
dichotomy theorem partition function holant problem holographic algorithms interpolation counting complexity