Revised: January 20, 2013

Published: February 26, 2013

**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]

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.