2
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – holf Dec 2 '16 at 8:26
9
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.