The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete

Details The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete

2005-01-12

arxiv.org/abs/math/0501176v1

Mathematics

Combinatorics

10 pages, 5 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The computation of Kostka Numbers and Littlewood-Richardson Coefficients is #P-complete will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-179723