Complexity and Completeness of Immanants
| dc.creator | Brylinski, Jean-Luc | |
| dc.creator | Brylinski, Ranee | |
| dc.date | 2003-01-23 | |
| dc.date | 2003-01-23 | |
| dc.date.accessioned | 2026-07-07T03:19:23Z | |
| dc.date.available | 2026-07-07T03:19:23Z | |
| dc.description | Immanants are polynomial functions of n by n matrices attached to irreducible characters of the symmetric group S_n, or equivalently to Young diagrams of size n. Immanants include determinants and permanents as extreme cases. Valiant proved that computation of permanents is a complete problem in his algebraic model of NP theory, i.e., it is VNP-complete. We prove that computation of immanants is VNP-complete if the immanants are attached to a family of diagrams whose separation is $Ω(n^δ)$ for some $δ>0$. We define the separation of a diagram to be the largest number of overhanging boxes contained in a single row. Our theorem proves a conjecture of Buergisser for a large variety of families, and in particular we recover with new proofs his VNP-completeness results for hooks and rectangles. | |
| dc.description | 10 pages, Latex | |
| dc.identifier | https://arxiv.org/abs/cs/0301024 | |
| dc.identifier | http://arxiv.org/abs/cs/0301024 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/31437 | |
| dc.subject | Computational Complexity | |
| dc.subject | Combinatorics | |
| dc.subject | F.1.3 ; F.2.3 | |
| dc.title | Complexity and Completeness of Immanants | |
| dc.type | text |