  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.
