License: Creative Commons Attribution-NoDerivs 3.0 Unported license (CC BY-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.STACS.2009.1821
URN: urn:nbn:de:0030-drops-18217
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2009/1821/
Go to the corresponding LIPIcs Volume Portal

Goldberg, Leslie Ann ; Grohe, Martin ; Jerrum, Mark ; Thurley, Marc

A Complexity Dichotomy for Partition Functions with Mixed Signs

pdf-format:
09001.GoldbergLeslieAnn.1821.pdf (0.2 MB)

Abstract

\emph{Partition functions}, also known as \emph{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 (2000) and Bulatov and Grohe (2005), 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 $\ensuremath{\mathbb{F}_2}$.

BibTeX - Entry

@InProceedings{goldberg_et_al:LIPIcs:2009:1821,
  author =	{Leslie Ann Goldberg and Martin Grohe and Mark Jerrum and Marc Thurley},
  title =	{{A Complexity Dichotomy for Partition Functions with Mixed Signs}},
  booktitle =	{26th International Symposium on Theoretical Aspects of Computer Science},
  pages =	{493--504},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-09-5},
  ISSN =	{1868-8969},
  year =	{2009},
  volume =	{3},
  editor =	{Susanne Albers and Jean-Yves Marion},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2009/1821},
  URN =		{urn:nbn:de:0030-drops-18217},
  doi =		{10.4230/LIPIcs.STACS.2009.1821},
  annote =	{Keywords: Computational complexity}
}

Keywords: Computational complexity
Collection: 26th International Symposium on Theoretical Aspects of Computer Science
Issue Date: 2009
Date of publication: 19.02.2009

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI