JOURNAL OF
ALGEBRAIC
COMBINATORICS

Home > Vol 24, No 3 (2006)

Hariharan Narayanan

University of Chicago Department of Computer Science Chicago USA Chicago USA

Kostka numbers and Littlewood-Richardson coefficients appear in combinatorics and representation theory. Interest in their computation stems from the fact that they are present in quantum mechanical computations since Wigner [15]. In recent times, there have been a number of algorithms proposed to perform this task [1-3, 11, 12]. The issue of their computational complexity has received at-tention in the past, and was raised recently by E. Rassart in [11]. We prove that the problem of computing either quantity is # P-complete. Thus, unless P = NP, which is widely disbelieved, there do not exist efficient algorithms that compute these numbers.

1. A. Barvinok and S.V. Fomin, Sparse interpolation of symmetric polynomials, Advances in Applied Mathematics 18 (1997), 271-285, MR 98i:05164.
2. S. Billey, V. Guillemin, and E. Rassart, “A vector partition function for the multiplicities of slk (C),” Journal of Algebra 278(1) (2004), 251-293.
3. C. Cochet, Kostka Numbers and Littlewood-Richardson Coefficients, preprint (2003).
4. M. Dyer, R. Kannan, and J. Mount, Sampling contingency tables, Random Structures and Algorithms 10 (1997), 487-506.
5. W. Fulton, “Young Tableaux,” London Mathematical Society Student Texts 35 (1997).
6. D. E. Knuth, “Permutations, matrices, and generalized Young tableaux,” Pacific Journal of Mathematics 34 (1970), 709-727.
7. A. Knutson and T. Tao, “The honeycomb model of tensor products I: Proof of the saturation conjecture,” J. Amer. Math. Soc. 12 (1999), 1055-1090.
8. K. Mulmuley and M, Sohoni, “Geometric Complexity III: on deciding positivity of Littlewood- Richardson coefficients,” http://arxiv.org/abs/cs.CC/0501076
9. K. Mulmuley and M. Sohoni, “Geometric complexity theory, P vs. NP, and explicit obstructions.,” in Proceedings, International Conference on Algebra and Geometry, Hyderabad (2001).
10. I. Pak and E. Vallejo, “Combinatorics and geometry of Littlewood-Richardson cones,” Europ. J. Combinatorics 26 (2005), 995-1008.
11. E. Rassart, “Geometric approaches to computing Kostka numbers and Littlewood-Richardson coefficients,” Thesis for the Ph.D. degree in Mathematics, Massachusetts Institute of Technology (MIT), 2004.
12. E. Rassart, “A polynomiality property for Littlewood-Richardson coefficients,” Journal of Combinatorial Theory, Series A 107(2) (2004), 161-179.
13. L.G. Valiant, “The complexity of computing the permanent,” Theoret. Comp. Sci. 8 (1979), 189-201.
14. M.A.A. van Leeuwen, “The Littlewood-Richardson rule, and related combinatorics,” Math. Soc. of Japan Memoirs 11, Interaction of Combinatorics and Representation Theory; arXiv:math.CO/9908099.
15. E. Wigner, “On the consequences of the symmetry of the nuclear Hamiltonian on the spectroscopy of the nuclei,” Physical Review 51 (1937), 106-119.