Computer Science – Computational Complexity
Scientific paper
2003-01-23
Computer Science
Computational Complexity
10 pages, Latex
Scientific paper
Immanants are polynomial functions of n by n matrices attached to irreducible characters of the symmetric group S_n, or equivalently to Young diagrams of size n. Immanants include determinants and permanents as extreme cases. Valiant proved that computation of permanents is a complete problem in his algebraic model of NP theory, i.e., it is VNP-complete. We prove that computation of immanants is VNP-complete if the immanants are attached to a family of diagrams whose separation is $\Omega(n^\delta)$ for some $\delta>0$. We define the separation of a diagram to be the largest number of overhanging boxes contained in a single row. Our theorem proves a conjecture of Buergisser for a large variety of families, and in particular we recover with new proofs his VNP-completeness results for hooks and rectangles.
Brylinski Jean-Luc
Brylinski Ranee
No associations
LandOfFree
Complexity and Completeness of Immanants 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 Complexity and Completeness of Immanants, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Complexity and Completeness of Immanants will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-709544