Loading…
The Complexity of Partition Functions on Hermitian Matrices
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 g...
Saved in:
Published in: | arXiv.org 2010-04 |
---|---|
Main Author: | |
Format: | Article |
Language: | English |
Subjects: | |
Online Access: | Get full text |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
cited_by | |
---|---|
cites | |
container_end_page | |
container_issue | |
container_start_page | |
container_title | arXiv.org |
container_volume | |
creator | Thurley, Marc |
description | 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. |
format | article |
fullrecord | <record><control><sourceid>proquest</sourceid><recordid>TN_cdi_proquest_journals_2087239556</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>2087239556</sourcerecordid><originalsourceid>FETCH-proquest_journals_20872395563</originalsourceid><addsrcrecordid>eNpjYuA0MjY21LUwMTLiYOAtLs4yMDAwMjM3MjU15mSwDslIVXDOzy3ISa3ILKlUyE9TCEgsKsksyczPU3ArzUsGMYoVgByP1KJcoHBinoJvYklRZnJqMQ8Da1piTnEqL5TmZlB2cw1x9tAtKMovLE0tLonPyi8tygNKxRsZWJgbGVuampoZE6cKAAGJN0s</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>2087239556</pqid></control><display><type>article</type><title>The Complexity of Partition Functions on Hermitian Matrices</title><source>Publicly Available Content Database</source><creator>Thurley, Marc</creator><creatorcontrib>Thurley, Marc</creatorcontrib><description>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.</description><identifier>EISSN: 2331-8422</identifier><language>eng</language><publisher>Ithaca: Cornell University Library, arXiv.org</publisher><subject>Combinatorial analysis ; Complexity ; Graphical representations ; Group theory ; Homomorphisms ; Invariants ; Mathematical analysis ; Matrix methods ; Partitions ; Partitions (mathematics) ; Polynomials ; Spin glasses</subject><ispartof>arXiv.org, 2010-04</ispartof><rights>2010. This work is published under http://arxiv.org/licenses/nonexclusive-distrib/1.0/ (the “License”). Notwithstanding the ProQuest Terms and Conditions, you may use this content in accordance with the terms of the License.</rights><oa>free_for_read</oa><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.proquest.com/docview/2087239556?pq-origsite=primo$$EHTML$$P50$$Gproquest$$Hfree_for_read</linktohtml><link.rule.ids>780,784,25753,37012,44590</link.rule.ids></links><search><creatorcontrib>Thurley, Marc</creatorcontrib><title>The Complexity of Partition Functions on Hermitian Matrices</title><title>arXiv.org</title><description>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.</description><subject>Combinatorial analysis</subject><subject>Complexity</subject><subject>Graphical representations</subject><subject>Group theory</subject><subject>Homomorphisms</subject><subject>Invariants</subject><subject>Mathematical analysis</subject><subject>Matrix methods</subject><subject>Partitions</subject><subject>Partitions (mathematics)</subject><subject>Polynomials</subject><subject>Spin glasses</subject><issn>2331-8422</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>2010</creationdate><recordtype>article</recordtype><sourceid>PIMPY</sourceid><recordid>eNpjYuA0MjY21LUwMTLiYOAtLs4yMDAwMjM3MjU15mSwDslIVXDOzy3ISa3ILKlUyE9TCEgsKsksyczPU3ArzUsGMYoVgByP1KJcoHBinoJvYklRZnJqMQ8Da1piTnEqL5TmZlB2cw1x9tAtKMovLE0tLonPyi8tygNKxRsZWJgbGVuampoZE6cKAAGJN0s</recordid><startdate>20100407</startdate><enddate>20100407</enddate><creator>Thurley, Marc</creator><general>Cornell University Library, arXiv.org</general><scope>8FE</scope><scope>8FG</scope><scope>ABJCF</scope><scope>ABUWG</scope><scope>AFKRA</scope><scope>AZQEC</scope><scope>BENPR</scope><scope>BGLVJ</scope><scope>CCPQU</scope><scope>DWQXO</scope><scope>HCIFZ</scope><scope>L6V</scope><scope>M7S</scope><scope>PIMPY</scope><scope>PQEST</scope><scope>PQQKQ</scope><scope>PQUKI</scope><scope>PRINS</scope><scope>PTHSS</scope></search><sort><creationdate>20100407</creationdate><title>The Complexity of Partition Functions on Hermitian Matrices</title><author>Thurley, Marc</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-proquest_journals_20872395563</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>2010</creationdate><topic>Combinatorial analysis</topic><topic>Complexity</topic><topic>Graphical representations</topic><topic>Group theory</topic><topic>Homomorphisms</topic><topic>Invariants</topic><topic>Mathematical analysis</topic><topic>Matrix methods</topic><topic>Partitions</topic><topic>Partitions (mathematics)</topic><topic>Polynomials</topic><topic>Spin glasses</topic><toplevel>online_resources</toplevel><creatorcontrib>Thurley, Marc</creatorcontrib><collection>ProQuest SciTech Collection</collection><collection>ProQuest Technology Collection</collection><collection>Materials Science & Engineering Collection</collection><collection>ProQuest Central (Alumni)</collection><collection>ProQuest Central</collection><collection>ProQuest Central Essentials</collection><collection>ProQuest Central</collection><collection>Technology Collection</collection><collection>ProQuest One Community College</collection><collection>ProQuest Central</collection><collection>SciTech Premium Collection</collection><collection>ProQuest Engineering Collection</collection><collection>Engineering Database</collection><collection>Publicly Available Content Database</collection><collection>ProQuest One Academic Eastern Edition (DO NOT USE)</collection><collection>ProQuest One Academic</collection><collection>ProQuest One Academic UKI Edition</collection><collection>ProQuest Central China</collection><collection>Engineering Collection</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Thurley, Marc</au><format>book</format><genre>document</genre><ristype>GEN</ristype><atitle>The Complexity of Partition Functions on Hermitian Matrices</atitle><jtitle>arXiv.org</jtitle><date>2010-04-07</date><risdate>2010</risdate><eissn>2331-8422</eissn><abstract>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.</abstract><cop>Ithaca</cop><pub>Cornell University Library, arXiv.org</pub><oa>free_for_read</oa></addata></record> |
fulltext | fulltext |
identifier | EISSN: 2331-8422 |
ispartof | arXiv.org, 2010-04 |
issn | 2331-8422 |
language | eng |
recordid | cdi_proquest_journals_2087239556 |
source | Publicly Available Content Database |
subjects | Combinatorial analysis Complexity Graphical representations Group theory Homomorphisms Invariants Mathematical analysis Matrix methods Partitions Partitions (mathematics) Polynomials Spin glasses |
title | The Complexity of Partition Functions on Hermitian Matrices |
url | http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T15%3A34%3A48IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=document&rft.atitle=The%20Complexity%20of%20Partition%20Functions%20on%20Hermitian%20Matrices&rft.jtitle=arXiv.org&rft.au=Thurley,%20Marc&rft.date=2010-04-07&rft.eissn=2331-8422&rft_id=info:doi/&rft_dat=%3Cproquest%3E2087239556%3C/proquest%3E%3Cgrp_id%3Ecdi_FETCH-proquest_journals_20872395563%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=2087239556&rft_id=info:pmid/&rfr_iscdi=true |