The computational complexity of immanants

Permanents and determinants are special cases of immanants. The latter are polynomial matrix functions defined in terms of characters of symmetric gro ups and corresponding to Young diagrams. Valiant has proved that the evalua tion of permanents is a complete problem in both the Turing machine model ( #P-completeness) as well as in his algebraic model (VNP-completeness). We s how that the evaluation of immanants corresponding to hook diagrams or rect angular diagrams of polynomially growing width is both #P-complete and VNP- complete.