Computando lo permanente
En álgebra lineal , el cálculo de la permanente de una matriz es un problema que se cree que es más difícil que el cálculo del determinante de una matriz a pesar de la aparente similitud de las definiciones.
El permanente se define de manera similar al determinante, como una suma de productos de conjuntos de entradas de la matriz que se encuentran en distintas filas y columnas. Sin embargo, cuando el determinante pondera cada uno de estos productos con un signo de ± 1 basado en la paridad del conjunto , el permanente los pondera a todos con un signo de +1.
Si bien el determinante se puede calcular en tiempo polinomial mediante eliminación gaussiana , generalmente se cree que el permanente no se puede calcular en tiempo polinomial. En la teoría de la complejidad computacional , un teorema de Valiant establece que calcular permanentes es # P-difícil , e incluso # P-completo para matrices en las que todas las entradas son 0 o 1 Valiant (1979) . Esto coloca el cálculo de lo permanente en una clase de problemas que se cree que son incluso más difíciles de calcular que NP . Se sabe que calcular el permanente es imposible para los circuitos ACC 0 uniformes en el espacio logarítmico ( Allender & Gore 1994)
El desarrollo de algoritmos tanto exactos como aproximados para calcular el permanente de una matriz es un área activa de investigación.
La suma aquí se extiende a todos los elementos σ del grupo simétrico S n , es decir, a todas las permutaciones de los números 1, 2, ..., n . Esta fórmula se diferencia de la fórmula correspondiente para el determinante solo en que, en el determinante, cada producto se multiplica por el signo de la permutación σ, mientras que en esta fórmula cada producto no tiene signo. La fórmula puede traducirse directamente en un algoritmo que amplía ingenuamente la fórmula, sumando todas las permutaciones y dentro de la suma multiplicando cada entrada de la matriz. Esto requiere n! n operaciones aritméticas.
El algoritmo exacto general más conocido [1] se debe a HJ Ryser ( 1963 ). El método de Ryser se basa en una fórmula de inclusión-exclusión que se puede dar [2] de la siguiente manera: Sea obtenido de A eliminando k columnas, sea el producto de las sumas de fila de , y sea la suma de los valores de sobre todo lo posible . Entonces
