Para el lector interesado, señalemos simplemente las similitudes entre el determinante y el permanente. Dado un $n \times n$ matriz $A$ el determinante de $A$ es: $$\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)}$$ donde $\mathfrak S_n$ es el grupo simétrico en $n$ elementos, por lo que $\sigma \in \mathfrak S_n$ es una permutación de $\{1,2,\dots,n\}$ .
La permanente de $A$ es: $$\operatorname{perm}_n(A) = \sum_{\sigma \in \mathfrak S_n} a_{1,\sigma(1)} a_{2,\sigma(2)} \cdots a_{n, \sigma(n)}$$ por lo que las similitudes son ahora obvias: simplemente eliminamos el $\operatorname{sign}(\sigma)$ de la fórmula del determinante para obtener la fórmula de la permanente.
En la fórmula del $\operatorname{det}_n$ tenemos una suma de $n!$ (el orden de $\mathfrak S_n$ ). Cada término tiene $n$ factores, por lo que para calcular el determinante de forma ingenua necesitamos $(n-1)(n!)$ multiplicaciones y $n! - 1$ adiciones. Es decir, tenemos una complejidad muy mala para un algoritmo ingenuo.
Sin embargo, podemos calcular el determinante mediante una descomposición LU, $PA = LU$ Así que $\operatorname{det}_n(A)$ es el producto de los elementos diagonales de $U$ multiplicado por $\pm 1$ . Se sabe que la complejidad de la descomposición LU es polinómica, entre $\mathcal O(n^2)$ y $\mathcal O(n^3)$ (depende de la rapidez con la que puedas multiplicar matrices).
Nuestro análisis ingenuo de la $\operatorname{det}_n$ se extiende a $\operatorname{perm}_n$ Sin embargo, para los permanentes no hay conocido "truco" para calcularlo en tiempo polinómico.
Se sabe que el cálculo de la permanente de un $(0,1)$ -matriz es $NP$ -duro y #P-completo . #P es la clase de complejidad de problemas de conteo asociados a los problemas de decisión en $NP$ . Un algoritmo de tiempo polinómico para la permanente implicaría que FP \= #P (lo que implicaría $P = NP$ ).
Un ejemplo de problema de decisión en $NP$ es decidir si un gráfico dado tiene un Trayectoria hamiltoniana . El problema de recuento correspondiente sería decir cuántos Las trayectorias hamiltonianas existen.
Un documento básico sobre esto es Leslie G. Valiant, "The Complexity of Computing the Permanent" en Informática teórica 8(2), páginas 189-201, donde se definió la clase #P y se demostró que el cálculo de la permanente es #P-completo.
La gente en teoría de la complejidad algebraica tienen un punto de vista diferente. En la teoría de la complejidad algebraica, nos ocupamos básicamente de lo difícil que es evaluar polinomios (nótese que tanto $\operatorname{det}_n$ y $\operatorname{perm}_n$ son polinomios).
En la teoría de la complejidad algebraica, existen otras clases de complejidad algebraica, que se describen en el artículo de Wikipedia sobre complejidad del circuito aritmético . Tenemos los análogos algebraicos de $P$ y $NP$ , llamado $VP$ y $VNP$ . Los miembros de $VP$ y $VNP$ son secuencias de polinomios.
No se sabe si $\operatorname{det}_n$ es $VP$ -completa, pero está claro que la secuencia está en $VP$ . Se sabe que $\operatorname{perm}_n$ es $VNP$ -completa.
4 votos
Para los que no conocen el término permanente: aquí está la entrada de Wikipedia . Se define con una fórmula que es exactamente como la del determinante, pero sin el "signo" de la permutación. Así, la permanente de la matriz $\begin{pmatrix} a & b\\ c & d\end{pmatrix}$ es $ad + bc$ .
4 votos
El determinante es la función unitaria escalada, antisimétrica y multilineal de los vectores. La permanente es la función unitaria, simétrica y multilineal de los vectores. El intercambio de filas de la matriz cambia el signo del determinante, pero no cambia el signo de la permanente. Los determinantes se pueden calcular en tiempo polinómico. Las permanentes no se saben calcular en tiempo polinómico. Este es otro de esos problemas en los que una versión es fácilmente politómica y la otra es frustrantemente difícil, como 2-sat vs 3-sat.