The complexity of computing Kronecker coefficients
Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2008-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/3622/pdf |
| _version_ | 1797270422431989760 |
|---|---|
| author | Peter Bürgisser Christian Ikenmeyer |
| author_facet | Peter Bürgisser Christian Ikenmeyer |
| author_sort | Peter Bürgisser |
| collection | DOAJ |
| description | Kronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem $\mathrm{KRONCOEFF}$ of computing Kronecker coefficients is very difficult. More specifically, we prove that $\mathrm{KRONCOEFF}$ is #$\mathrm{P}$-hard and contained in the complexity class $\mathrm{GapP}$. Formally, this means that the existence of a polynomial time algorithm for $\mathrm{KRONCOEFF}$ is equivalent to the existence of a polynomial time algorithm for evaluating permanents. |
| first_indexed | 2024-04-25T02:04:01Z |
| format | Article |
| id | doaj.art-6aff6268091a48d9b7b867857991775f |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T02:04:01Z |
| publishDate | 2008-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-6aff6268091a48d9b7b867857991775f2024-03-07T14:38:06ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502008-01-01DMTCS Proceedings vol. AJ,...Proceedings10.46298/dmtcs.36223622The complexity of computing Kronecker coefficientsPeter Bürgisser0Christian Ikenmeyer1Mathematisches Institut der Universität PaderbornMathematisches Institut der Universität PaderbornKronecker coefficients are the multiplicities in the tensor product decomposition of two irreducible representations of the symmetric group $S_n$. They can also be interpreted as the coefficients of the expansion of the internal product of two Schur polynomials in the basis of Schur polynomials. We show that the problem $\mathrm{KRONCOEFF}$ of computing Kronecker coefficients is very difficult. More specifically, we prove that $\mathrm{KRONCOEFF}$ is #$\mathrm{P}$-hard and contained in the complexity class $\mathrm{GapP}$. Formally, this means that the existence of a polynomial time algorithm for $\mathrm{KRONCOEFF}$ is equivalent to the existence of a polynomial time algorithm for evaluating permanents.https://dmtcs.episciences.org/3622/pdfrepresentations of symmetric groupstensor productskronecker coefficientscomputational complexity[math.math-co] mathematics [math]/combinatorics [math.co][info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Peter Bürgisser Christian Ikenmeyer The complexity of computing Kronecker coefficients Discrete Mathematics & Theoretical Computer Science representations of symmetric groups tensor products kronecker coefficients computational complexity [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | The complexity of computing Kronecker coefficients |
| title_full | The complexity of computing Kronecker coefficients |
| title_fullStr | The complexity of computing Kronecker coefficients |
| title_full_unstemmed | The complexity of computing Kronecker coefficients |
| title_short | The complexity of computing Kronecker coefficients |
| title_sort | complexity of computing kronecker coefficients |
| topic | representations of symmetric groups tensor products kronecker coefficients computational complexity [math.math-co] mathematics [math]/combinatorics [math.co] [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/3622/pdf |
| work_keys_str_mv | AT peterburgisser thecomplexityofcomputingkroneckercoefficients AT christianikenmeyer thecomplexityofcomputingkroneckercoefficients AT peterburgisser complexityofcomputingkroneckercoefficients AT christianikenmeyer complexityofcomputingkroneckercoefficients |