Computer Science – Computational Complexity
Scientific paper
2010-04-07
Computer Science
Computational Complexity
Scientific paper
Partition functions of certain classes of "spin glass" models in statistical physics show strong connections to combinatorial graph invariants. Also known as homomorphism functions they allow for the representation of many such invariants, for example, the number of independent sets of a graph or the number nowhere zero k-flows. Contributing to recent developments on the complexity of partition functions we study the complexity of partition functions with complex values. These functions are usually determined by a square matrix A and it was shown by Goldberg, Grohe, Jerrum, and Thurley that for each real-valued symmetric matrix, the corresponding partition function is either polynomial time computable or #P-hard. Extending this result, we give a complete description of the complexity of partition functions definable by Hermitian matrices. These can also be classified into polynomial time computable and #P-hard ones. Although the criterion for polynomial time computability is not describable in a single line, we give a clear account of it in terms of structures associated with Abelian groups.
No associations
LandOfFree
The Complexity of Partition Functions on Hermitian Matrices does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with The Complexity of Partition Functions on Hermitian Matrices, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Complexity of Partition Functions on Hermitian Matrices will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-396597