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