direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Page Content

There is no English translation for this web page.

Search for Publication

Search for publications

All Publications

The computational complexity of immanants
Citation key B-The-Computational-Complexity-Of-Immanants
Author Peter Bürgisser
Pages 1023-1040
Year 2000
Journal SIAM J. Comp.
Volume 30
Number 3
Abstract Permanents and determinants are special cases of immanants. The latter are polynomial matrix functions defined in terms of the characters of the symmetric groups and corresponding to Young diagrams. Valiant has proved that the evaluation of permanents is a complete problem in both the Turing machine model (#P-completeness) as well as in his algebraic model (VNP-completeness). We show that the evaluation of immanants corresponding to hook diagrams or rectangular diagrams of poynomially growing width is both #P-complete and VNP-complete.
Link to publication Download Bibtex entry

Zusatzinformationen / Extras

Quick Access:

Schnellnavigation zur Seite über Nummerneingabe

This site uses Matomo for anonymized webanalysis. Visit Data Privacy for more information and opt-out options.