Càlcul del permanent

En àlgebra llineal, el càlcul del permanent d'una matriu és un problema que es pensa que és més difícil que el càlcul del determinant d'una matriu, a pesar de l'aparent similitut de les definicions.

El permanent es definix de forma similar al determinant, com la suma de productes de conjunts d'elements de la matriu ubicats en files i columnes distintes. No obstant, si el determinant pondera cada u d'estos productes en un signe ±1 basat en la paritat dels elements, el permanent els pondera a tots en un signe +1.

Si ben el determinant pot calcular-se en temps polinòmic per mig de l'eliminació de Gauss-Jordan, generalment es creu que el permanent no pot calcular-se en temps polinòmic. En teoria de la complexitat computacional, una teorema de Valiant establix que calcular permanents és #P-difícil, i inclús #P-complet per a matrius a on tots els elements són 0 o 1 Valiant (1979). Açò situa el càlcul del permanent en una classe de problemes que es considera encara més difícil de calcular que NP. Se sap que calcular el permanent és impossible per a circuits ACC⁰ uniformes en l'espai logarítmic. Allender (Gore)

El desenroll d'algoritmes exactes i aproximats per a calcular el permanent d'una matriu és un àrea d'investigació activa.

Definició i algoritme ingenu

El permanent d'una matriu de n per n, A = (a_i,j), es definix com:

$\mathrm{perm}(A)=\sum _{\sigma \in S_n}\prod _{i=1}^n{a}_{i,\sigma (i)}.$

La suma s'estén a tots els elements σ del grup simètric S_n, és dir, a totes les permutació dels números 1, 2, ..., n. Esta fòrmula diferix de la fòrmula corresponent per al determinant sol en que, en el determinant, cada producte es multiplica pel signe de la permutació σ, mentres que en esta fòrmula cada producte no té signe. La fòrmula pot traduir-se directament a un algoritme que l'expandix de forma ingènua, sumant totes les permutació i, dins de la suma, multiplicant cada entrada de la matriu. Açò requerix n!·n operacions aritmètiques.

Fòrmula de Ryser

L'algoritme exacte general més conegut es deu a Ryser (1963). El método de Ryser es basa en la fòrmula d'inclusió-exclusió, que es pot expressar com de la següent manera: siga $A_k$ obtingut de A eliminant k columnes, siga $P(A_k)$ el producte de les sumes de files de $A_k$ i siga ${\Sigma }_k$ la suma dels valors de $P(A_k)$ sobre tots els valors possibles de $A_k$. Llavors: $\mathrm{perm}(A)=\sum _{k=0}^{n-1}(-1{)}^k{\Sigma }_k.$

Pot reescriure's en térmens de les entrades de la matriu de la següent manera:

$\mathrm{perm}(A)=(-1{)}^n\sum _{S\subseteq \{1,\dots ,n\}}(-1{)}^{|S|}\prod _{i=1}^n\sum _{j\in S}{a}_{ij}.$

La fòrmula de Ryser es pot calcular per mig de $O(2^{n-1}{n}^2)$ operacions aritmètiques, o $O(2^{n-1}n)$ processant els conjunts $S$ en orde segons el còdic Gray.