Metraipolis › archive › dc_d03bf9cf665e

Computing the permanent — Wikipedia (en)

Source
Wikipedia (en)
Original
https://en.wikipedia.org/wiki/Computing_the_permanent
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-06T16:30:31.301Z
SHA-256 of the archived text
420eb751ca5783cdaae31fd50130ed50d5e22063c17c915cba56d1565bca5330
Stable URL of this page
https://metraipolis.com/documento/dc_d03bf9cf665e

How to cite

Computing the permanent — Wikipedia (en) — Wikipedia (en), https://en.wikipedia.org/wiki/Computing_the_permanent (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d03bf9cf665e (Metraipolis archive dc_d03bf9cf665e, sha256 420eb751ca5783cdaae31fd50130ed50d5e22063c17c915cba56d1565bca5330)
BibTeX
@misc{dcd03bf9cf665e,
  title = {Computing the permanent — Wikipedia (en)},
  howpublished = {Wikipedia (en)},
  url = {https://en.wikipedia.org/wiki/Computing_the_permanent},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d03bf9cf665e; sha256 420eb751ca5783cdaae31fd50130ed50d5e22063c17c915cba56d1565bca5330},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (en), https://en.wikipedia.org/wiki/Computing_the_permanent. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 Valiant (1979). 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.(Allender & Gore 1994) The development of both exact and approximate algorithms for computing the permanent of a matrix is an active area of research.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; categoria «Linear algebra»).
Fonte: Wikipedia in inglese, voce «Computing the permanent» — https://en.wikipedia.org/wiki/Computing_the_permanent
Wikidata Q5157642 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q5157642
Autori: i contributori di Wikipedia (cronologia: https://en.wikipedia.org/wiki/Computing_the_permanent?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 1369582133, consultata il 2026-10-06T15:17:32.740Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: d6869f0a085e54e6ba3b88417843d737d4649d566fb56a9b0579b3b575e21e25