Theory of Computing
-------------------
Title : The Complexity of the Fermionant and Immanants of Constant Width
Authors : Stephan Mertens and Cristopher Moore
Volume : 9
Number : 6
Pages : 273-282
URL : http://www.theoryofcomputing.org/articles/v009a006
Abstract
--------
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.