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

Question

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.

Answer 1

I extend my comment in an answer.

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.

Hyperdeterminants (https://en.wikipedia.org/wiki/Hyperdeterminant) is a generalization of determinants to tensors. See "New algorithms for linear k-matroid intersection and matroid k-parity problems" by A. Barvinok for identities and algorithms on hyperdeterminants.