Skip to Main content Skip to Navigation
Conference papers

A Complexity Dichotomy for Partition Functions with Mixed Signs

Abstract : Partition functions, also known as homomorphism functions, form a rich family of graph invariants that contain combinatorial invariants such as the number of k-colourings or the number of independent sets of a graph and also the partition functions of certain “spin glass” models of statistical physics such as the Ising model. Building on earlier work by Dyer and Greenhill [7] and Bulatov and Grohe [6], we completely classify the computational complexity of partition functions. Our main result is a dichotomy theorem stating that every partition function is either computable in polynomial time or #P-complete. Partition functions are described by symmetric matrices with real entries, and we prove that it is decidable in polynomial time in terms of the matrix whether a given partition function is in polynomial time or #P-complete. While in general it is very complicated to give an explicit algebraic or combinatorial description of the tractable cases, for partition functions described by a Hadamard matrices — these turn out to be central in our proofs — we obtain a simple algebraic tractability criterion, which says that the tractable cases are those “representable” by a quadratic polynomial over the field F2.
Document type :
Conference papers
Complete list of metadata

Cited literature [20 references]  Display  Hide  Download

https://hal.inria.fr/inria-00359820
Contributor : Publications Loria <>
Submitted on : Monday, February 9, 2009 - 2:35:23 PM
Last modification on : Monday, June 15, 2020 - 12:00:33 PM
Long-term archiving on: : Tuesday, June 8, 2010 - 10:07:13 PM

File

41-goldberg.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : inria-00359820, version 1

Collections

Citation

Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley. A Complexity Dichotomy for Partition Functions with Mixed Signs. 26th International Symposium on Theoretical Aspects of Computer Science STACS 2009, Feb 2009, Freiburg, Germany. pp.493-504. ⟨inria-00359820⟩

Share

Metrics

Record views

133

Files downloads

404