Estudiando un poco sobre el determinante y la permanente, me dicen que aunque ambos conceptos tienen fórmulas muy parecidas, la permanente no tenía mucho interés históricamente - fue hasta más tarde que los teóricos de la complejidad empezaron a sentir más curiosidad por ella.
¿Qué es exactamente lo que lo hace interesante para los teóricos de la complejidad? He oído que no hay ningún algoritmo eficiente para calcularlo, ¿es eso lo que quieren decir?
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.
Sólo una pregunta rápida: en caso de $LU$ -descomposición, no significa que para $A = LPU$ se deduce que ${\rm det} A$ tiene el mismo valor absoluto que ${\rm det } P$ (que es igual a un producto de entradas diagonales), no como $U$ ?
Evgeny, vaya, parece que me he equivocado, gracias por señalarlo. Quería decir que $PA = LU$ para una matriz de permutación $P$ .
$\text{#}P = FP$ debe implicar $P = NP$ porque la capacidad de conocer el número de soluciones de un SAT te diría trivialmente si hay una solución, ¿no?
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
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.