Why is the permanent of interest for complexity theorists?

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.