About: Computing the permanent

An Entity of Type: disease, from Named Graph: http://dbpedia.org, within Data Space: dbpedia.org

In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions. The permanent is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant weights each of these products with a ±1 sign based on the parity of the set, the permanent weights them all with a +1 sign.

Property Value
dbo:abstract
  • In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions. The permanent is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant weights each of these products with a ±1 sign based on the parity of the set, the permanent weights them all with a +1 sign. While the determinant can be computed in polynomial time by Gaussian elimination, it is generally believed that the permanent cannot be computed in polynomial time. In computational complexity theory, a theorem of Valiant states that computing permanents is #P-hard, and even #P-complete for matrices in which all entries are 0 or 1 . This puts the computation of the permanent in a class of problems believed to be even more difficult to compute than NP. It is known that computing the permanent is impossible for logspace-uniform ACC0 circuits. The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research. (en)
dbo:wikiPageExternalLink
dbo:wikiPageID
  • 20749642 (xsd:integer)
dbo:wikiPageLength
  • 28379 (xsd:nonNegativeInteger)
dbo:wikiPageRevisionID
  • 1056489773 (xsd:integer)
dbo:wikiPageWikiLink
dbp:authorlink
  • H. J. Ryser (en)
dbp:first
  • H. J. (en)
dbp:last
  • Ryser (en)
dbp:wikiPageUsesTemplate
dbp:year
  • 1963 (xsd:integer)
dcterms:subject
gold:hypernym
rdf:type
rdfs:comment
  • In linear algebra, the computation of the permanent of a matrix is a problem that is thought to be more difficult than the computation of the determinant of a matrix despite the apparent similarity of the definitions. The permanent is defined similarly to the determinant, as a sum of products of sets of matrix entries that lie in distinct rows and columns. However, where the determinant weights each of these products with a ±1 sign based on the parity of the set, the permanent weights them all with a +1 sign. (en)
rdfs:label
  • Computing the permanent (en)
owl:sameAs
prov:wasDerivedFrom
foaf:isPrimaryTopicOf
is dbo:wikiPageRedirects of
is dbo:wikiPageWikiLink of
is foaf:primaryTopic of
Powered by OpenLink Virtuoso    This material is Open Knowledge     W3C Semantic Web Technology     This material is Open Knowledge    Valid XHTML + RDFa
This content was extracted from Wikipedia and is licensed under the Creative Commons Attribution-ShareAlike 3.0 Unported License