direkt zum Inhalt springen

direkt zum Hauptnavigationsmenü

Sie sind hier

TU Berlin

Inhalt des Dokuments

Search for Publication

Suche nach Publikationen




All Publications

The computational complexity of immanants
Zitatschlüssel B-The-Computational-Complexity-Of-Immanants
Autor Peter Bürgisser
Seiten 1023-1040
Jahr 2000
Journal SIAM J. Comp.
Jahrgang 30
Nummer 3
Zusammenfassung 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 zur Publikation Download Bibtex Eintrag

Zusatzinformationen / Extras

Direktzugang

Schnellnavigation zur Seite über Nummerneingabe