The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete
| dc.creator | Narayanan, Hariharan | |
| dc.date | 2005-01-12 | |
| dc.date.accessioned | 2026-07-07T05:16:00Z | |
| dc.date.available | 2026-07-07T05:16:00Z | |
| dc.description | Kostka numbers and Littlewood-Richardson coefficients play an essential role in the representation theory of the symmetric groups and the special linear groups. There has been a significant amount of interest in their computation. The issue of their computational complexity has been a question of folklore, but was asked explicitly by E. Rassart. We prove that the computation of either quantity is #P-complete. The reduction to computing Kostka numbers, is from the #P-complete problem of counting the number of 2 x k contingency tables having given row and column sums. The main ingredient in this reduction is a correspondence discovered by D. E. Knuth. The reduction to the problem of computing Littlewood-Richardson coefficients is from that of computing Kostka numbers. | |
| dc.description | 10 pages, 5 figures | |
| dc.identifier | https://arxiv.org/abs/math/0501176 | |
| dc.identifier | http://arxiv.org/abs/math/0501176 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/73829 | |
| dc.subject | Combinatorics | |
| dc.subject | 05E15; 68Q17 | |
| dc.title | The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete | |
| dc.type | text |