pdf icon
Volume 9 (2013) Article 6 pp. 273-282 [Note]
The Complexity of the Fermionant and Immanants of Constant Width
Received: November 11, 2011
Revised: January 20, 2013
Published: February 26, 2013
Download article from ToC site:
[PDF (224K)] [PS (661K)] [Source ZIP]
Misc.:
[About the Authors] [HTML Bibliography] [BibTeX]
Keywords: fermionant, immanant, partition function, statistical physics, determinant, permanent, computational complexity, graph theory, representation theory
Categories: note, complexity theory, algebraic complexity, statistical physics, #P, parity-P, determinant, permanent, partition function, graphs, graphs - planar, representation theory
ACM Classification: F.2.1
AMS Classification: 68Q17

Abstract: [Plain Text Version]

$ \newcommand{\Ferm}{\mathrm{Ferm}} \newcommand{\Imm}{\mathrm{Imm}} \newcommand{\oplusP}{\oplus \mathrm{P}} \newcommand{\NP}{\mathrm{NP}} \newcommand{\RP}{\mathrm{RP}} $

In the context of statistical physics, Chandrasekharan and Wiese recently introduced the fermionant $\Ferm_k$, a determinant-like function of a matrix where each permutation $\pi$ is weighted by $-k$ raised to the number of cycles in $\pi$. We show that computing $\Ferm_k$ is #P-hard under polynomial-time Turing reductions for any constant $k > 2$, and is $\oplusP$-hard for $k=2$, where both results hold even for the adjacency matrices of planar graphs. As a consequence, unless the polynomial-time hierarchy collapses, it is impossible to compute the immanant $\Imm_\lambda \,A$ as a function of the Young diagram $\lambda$ in polynomial time, even if the width of $\lambda$ is restricted to be at most $2$. In particular, unless $\NP \subseteq \RP$, $\Ferm_2$ is not in P, and there are Young diagrams $\lambda$ of width $2$ such that $\Imm_\lambda$ is not in P.