<p>I extend my comment in an answer. </p>

<p>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}$).</p>

<p>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" (<a href="http://math-www.uni-paderborn.de/agpb/work/habil.ps" rel="nofollow noreferrer">http://math-www.uni-paderborn.de/agpb/work/habil.ps</a>). Nicolas de Rugy-Altherre studied the complexity of one of them, the Fermionant, and proves other $VNP$-completeness results for such functions in "<em>Determinant versus Permanent: salvation via generalization? The algebraic complexity of the Fermionant and the Immanant</em>", <a href="https://arxiv.org/abs/1309.2156" rel="nofollow noreferrer">https://arxiv.org/abs/1309.2156</a>.</p>

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

CC BY-SA 3.0
2016-12-02T14:45:16.407Z
Also see [Moore & Mertens](http://theoryofcomputing.org/articles/v009a006/) on the Fermionant and immanants.
Joshua Grochow
CC BY-SA 3.0
2016-12-02T09:24:02.187Z
2018-01-15T07:19:52.223Z
2018-01-15T07:19:52.223Z
holf
<p>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,</p>

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

<p>$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)$.</p>

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

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

CC BY-SA 3.0
2016-12-02T08:26:15.647Z
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 https://arxiv.org/abs/1309.2156.
holf
<cc.complexity-theory><physics><permanent><determinant>
Complexity of computing generalised determinants. (P - #P transition)
biryani
# Complexity of computing generalised determinants. (P - #P transition)

(Asked by: username_0 on 2016-12-02)

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.

**Tags:** cc.complexity-theory, physics, permanent, determinant
> **Comments:**
> **username_1**: 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 https://arxiv.org/abs/1309.2156.  

---

## 1 answers

### Answer by username_1 on 2016-12-02. Score: 9 | Accepted answer

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.

> **Comments:**
> **username_2**: Also see [Moore & Mertens](http://theoryofcomputing.org/articles/v009a006/) on the Fermionant and immanants.  

---

