# Complexity of computing generalised determinants. (P - #P transition)

Computing the determinant of a matrix can be done in polynomial time, while computing the permanent is known to be #P-hard. Let $A$ be an $n \times n$ matrix. Define a generalised determinant function as follows,

$$Det_ \theta (A) = \sum_ {\mu \in S_n} e^{i \theta ~ sign(\mu)} A_{1,\mu (1)} \ldots A_ {n , \mu(n)}$$.

$S_n$ is the symmetric group on $n$ elements. It can be readily seen that $Det_0 (A) = Perm(A)$ and $Det_{\pi/2}(A) = i Det(A)$.

• For what value of $\theta$ does the computation of $Det_\theta{A}$ cease to be #P-hard?
• For what value of $\theta$ does $Det_\theta{A}$ become poly time computable?
• As $\theta$ varies how does the complexity of computation of $Det_\theta{A}$ change in general?

ps - Some physics- Prima facie $Det_\theta{A}$ looks like the analogue of Slater determinant corresponding to Anyon wavefunctions.

• Don't we have $Det_\theta(A) = \cos(\theta)Perm(A)+i \sin(\theta)Det(A)$? Thus, if $\cos(\theta) \neq 0$, this is $\#P$-hard as you can compute $Det(A)$ in ptime. You may still be interested in Chapter 7 of Peter Bürgisser's Habilitationschrift "Completeness and reduction in Algebraic Complexity Theory" on the complexity of computing immanants and this paper arxiv.org/abs/1309.2156. – holf Dec 2 '16 at 8:26

By rewriting $e^{i \cdot sgn(\mu)\theta} = \cos(sgn(\mu)\theta)+i\sin(sgn(\mu)\theta) = \cos(\theta)+i \cdot sgn(\mu)\sin(\theta)$ we have: $Det_\theta(A) = \cos(\theta)Perm(A)+i\sin(\theta)Det(A)$. Thus, if $\cos(\theta) \neq 0$, we have $Perm(A) = (Det_\theta(A)-i\sin(\theta)Det(A))/\cos(\theta)$, meaning that $Det_\theta$ is $\#P$-hard (and $VNP$-complete over $\mathbb{C}$).
Several generalizations of the determinant have been studied however. Peter Bürgisser studies the complexity of immanants in his Habilitationschrift "Completeness and Reduction in Algebraic Complexity Theory" (http://math-www.uni-paderborn.de/agpb/work/habil.ps). Nicolas de Rugy-Altherre studied the complexity of one of them, the Fermionant, and proves other $VNP$-completeness results for such functions in "Determinant versus Permanent: salvation via generalization? The algebraic complexity of the Fermionant and the Immanant", https://arxiv.org/abs/1309.2156.