11
$\begingroup$

Studying a bit about the determinant and the permanent, I'm told that although both concepts have very similar formulas, the permanent was of not much interest historically - it was until later that complexity theorists became more curious about it.

What exactly makes it interesting for complexity theorists? I heard that there is no efficient algorithm to calculate it - is that what they mean?

$\endgroup$
  • 4
    $\begingroup$ For the benefit of those who are not aware of the term permanent: here's the Wikipedia entry. It is defined with a formula that is exactly like that of the determinant, but without the "sign" for the permutation. So that the permanent of the matrix $\begin{pmatrix} a & b\\ c & d\end{pmatrix}$ is $ad + bc$. $\endgroup$ – Willie Wong Apr 24 '14 at 8:01
  • 3
    $\begingroup$ The determinant is the unit scaled, anti-symmetric, multilinear function of vectors. The permanent is the unit-scaled, symmetric, multilinear function of vectors. Exchanging rows of matrix changes the sign of the determinant, it does not change the sign of a permanent. Determinants can be computed in polynomial time. Permanents are not known how to compute in polytime. This is another of those problems where one version is easily polytime and the other is frustratingly difficult, like 2-sat vs 3-sat. $\endgroup$ – DanielV May 1 '14 at 10:47
15
$\begingroup$

To the interested reader, let's just point out the similarities between the determinant and the permanent. Given a $n \times n$ matrix $A$, the determinant of $A$ is: $$\operatorname{det}_n(A) = \sum_{\sigma \in \mathfrak S_n} \operatorname{sign}(\sigma) a_{1,\sigma(1)} a_{2,\sigma(2)} \cdots a_{n, \sigma(n)}$$ where $\mathfrak S_n$ is the symmetric group on $n$ elements, so $\sigma \in \mathfrak S_n$ is a permutation of $\{1,2,\dots,n\}$.

The permanent of $A$ is: $$\operatorname{perm}_n(A) = \sum_{\sigma \in \mathfrak S_n} a_{1,\sigma(1)} a_{2,\sigma(2)} \cdots a_{n, \sigma(n)}$$ so the similarities are now obvious: we just remove the $\operatorname{sign}(\sigma)$ from the formula for the determinant to get the formula for the permanent.

In the formula for the $\operatorname{det}_n$, we have a sum of $n!$ (the order of $\mathfrak S_n$) terms. Each term has $n$ factors, so to compute the determinant naively we need $(n-1)(n!)$ multiplications and $n! - 1$ additions. I.e., we have very bad complexity for a naive algorithm.

However, we can compute the determinant by using an LU-decomposition, $PA = LU$, so $\operatorname{det}_n(A)$ is the product of the diagonal elements of $U$, multiplied by $\pm 1$. The complexity of LU-decomposition is well-known to be polynomial, between $\mathcal O(n^2)$ and $\mathcal O(n^3)$ (it depends on how fast you can multiply matrices).

Our naive analysis of the $\operatorname{det}_n$ extends to $\operatorname{perm}_n$, however, for the permanent there is no known "trick" to compute it in polynomial time.

It is known that computing the permanent of a $(0,1)$-matrix is $NP$-hard and #P-complete. #P is the complexity class of counting problems associated with decision problems in $NP$. A polynomial time algorithm for the permanent would imply that FP = #P (which would imply $P = NP$).

An example of a decision problem in $NP$ is to decide if a given graph has a Hamiltonian path. The corresponding counting problem would be to tell how many Hamiltonian paths there are.

A basic paper on this is Leslie G. Valiant, "The Complexity of Computing the Permanent" in Theoretical Computer Science 8(2), pages 189-201, wherein the class #P was defined and that computing the permanent was shown to be #P-complete.

People in algebraic complexity theory have a different viewpoint. In algebraic complexity theory, we basically deal with how difficult it is to evaluate polynomials (notice that both $\operatorname{det}_n$ and $\operatorname{perm}_n$ are polynomials).

In algebraic complexity theory, there are other algebraic complexity classes, which are described in the Wikipedia article on arithmetic circuit complexity. We have the algebraic analogues of $P$ and $NP$, called $VP$ and $VNP$. The members of $VP$ and $VNP$ are sequences of polynomials.

It is not known if $\operatorname{det}_n$ is $VP$-complete, but it is clear that the sequence is in $VP$. It is known that $\operatorname{perm}_n$ is $VNP$-complete.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Just a quick question: in case of $LU$-decomposition, doesn't that mean that for $A = LPU$ follows that ${\rm det} A$ has the same absolute value as ${\rm det } P$ (which is equal to a product of diagonal entries), not as $U$ ? $\endgroup$ – Evgeny Apr 20 '14 at 11:59
  • $\begingroup$ Evgeny, whoops, seems like I messed that up, thanks for pointing it out. I meant that $PA = LU$, for a permutation matrix $P$. $\endgroup$ – Calle Apr 20 '14 at 12:18
  • $\begingroup$ $\text{#}P = FP$ must imply $P = NP$ because the ability to know the number of solutions to a SAT would trivially tell you if there is a solution, no? $\endgroup$ – DanielV May 1 '14 at 10:40
  • $\begingroup$ DanielV, yes. Thanks. $\endgroup$ – Calle May 1 '14 at 11:05
  • 1
    $\begingroup$ I'll add that the permanent is of interest in quantum complexity because permanents are related to the time evolution of bosonic systems (e.g., photons). A bosonic quantum computer is a model of computation that might be between classical computers and quantum computers in terms of power. (scottaaronson.com/papers/optics.pdf) $\endgroup$ – Chris Chudzicki May 6 '14 at 1:00

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.