Geodesic
The complexity of computing Kronecker coefficients
Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) (2008).

Voir la notice de l'article provenant de la source Episciences

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. 
@article{DMTCS_2008_special_255_a30,
     author = {B\"urgisser, Peter and Ikenmeyer, Christian},
     title = {The complexity of computing {Kronecker} coefficients},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)},
     year = {2008},
     doi = {10.46298/dmtcs.3622},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3622/}
}
TY  - JOUR
AU  - Bürgisser, Peter
AU  - Ikenmeyer, Christian
TI  - The complexity of computing Kronecker coefficients
JO  - Discrete mathematics & theoretical computer science
PY  - 2008
VL  - DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3622/
DO  - 10.46298/dmtcs.3622
LA  - en
ID  - DMTCS_2008_special_255_a30
ER  - 
%0 Journal Article
%A Bürgisser, Peter
%A Ikenmeyer, Christian
%T The complexity of computing Kronecker coefficients
%J Discrete mathematics & theoretical computer science
%D 2008
%V DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008)
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3622/
%R 10.46298/dmtcs.3622
%G en
%F DMTCS_2008_special_255_a30
Bürgisser, Peter; Ikenmeyer, Christian. The complexity of computing Kronecker coefficients. Discrete mathematics & theoretical computer science, DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008), DMTCS Proceedings vol. AJ, 20th Annual International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2008) (2008). doi : 10.46298/dmtcs.3622. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.3622/

Cité par Sources :