Computando lo permanente

Problema en álgebra lineal

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 ⁰ uniformes en el espacio logs ( Allender & Gore 1994)

El desarrollo de algoritmos tanto exactos como aproximados para calcular la permanente de una matriz es un área activa de investigación.

Definición y algoritmo ingenuo

El permanente de una matriz n- por- n A = ( a _{i, j} ) se define como

${\displaystyle \operatorname {perm} (A)=\sum _{\sigma \in S_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}.}$

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.

Fórmula de Ryser

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 . Luego${\displaystyle A_{k}}$${\displaystyle P(A_{k})}$${\displaystyle A_{k}}$${\displaystyle \Sigma _{k}}$${\displaystyle P(A_{k})}$${\displaystyle A_{k}}$

${\displaystyle \operatorname {perm} (A)=\sum _{k=0}^{n-1}(-1)^{k}\Sigma _{k}.}$

Puede reescribirse en términos de las entradas de la matriz de la siguiente manera ^[3]

${\displaystyle \operatorname {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 se puede evaluar mediante operaciones aritméticas o procesando los conjuntos en el orden del código Gray . ^[4]${\displaystyle O(2^{n-1}n^{2})}$${\displaystyle O(2^{n-1}n)}$${\displaystyle S}$

Fórmula de Balasubramanian-Bax-Franklin-Glynn

Otra fórmula que parece ser tan rápida como la de Ryser (o quizás incluso el doble) se encuentra en los dos Ph.D. tesis ver ( Balasubramanian 1980 ), ( Bax 1998 ); también ( Bax y Franklin 1996 ). Los métodos para encontrar la fórmula son bastante diferentes, ya que están relacionados con la combinatoria del álgebra de Muir y con la teoría de diferencias finitas, respectivamente. Otra forma, relacionada con la teoría invariante, es a través de la identidad de polarización para un tensor simétrico ( Glynn 2010 ). La fórmula se generaliza a infinitos otros, como lo encuentran todos estos autores, aunque no está claro si son más rápidos que el básico. Ver ( Glynn 2013 ).

La fórmula conocida más simple de este tipo (cuando la característica del campo no es dos) es

${\displaystyle \operatorname {perm} (A)={\frac {1}{2^{n-1}}}\left[\sum _{\delta }\left(\prod _{k=1}^{n}\delta _{k}\right)\prod _{j=1}^{n}\sum _{i=1}^{n}\delta _{i}a_{ij}\right],}$

donde la suma externa está sobre todos los vectores .${\displaystyle 2^{n-1}}$${\displaystyle \delta =(\delta _{1}=1,\delta _{2},\dots ,\delta _{n})\in \{\pm 1\}^{n}}$

Casos especiales

Planar y K _3,3 -free

El número de emparejamientos perfectos en un gráfico bipartito se cuenta por el permanente de la matriz de biadjacencia del gráfico , y el permanente de cualquier matriz 0-1 se puede interpretar de esta manera como el número de emparejamientos perfectos en un gráfico. Para los gráficos planos (independientemente de la bipartidad), el algoritmo FKT calcula el número de emparejamientos perfectos en el tiempo polinomial cambiando los signos de un subconjunto cuidadosamente elegido de las entradas en la matriz de Tutte del gráfico, de modo que el Pfaffian del sesgo resultante matriz simétrica (la raíz cuadrada de su determinante) es el número de combinaciones perfectas. Esta técnica se puede generalizar a grafos que no contienen subgrafos homeomorfos al grafo bipartito completo K _3,3 . ^[5]

George Pólya había hecho la pregunta ^[6] de cuándo es posible cambiar los signos de algunas de las entradas de una matriz 01 A para que el determinante de la nueva matriz sea el permanente de A. No todas las matrices 01 son "convertibles" de esta forma; de hecho se sabe ( Marcus & Minc (1961) ) que no existe un mapa lineal tal que para todas las matrices . La caracterización de matrices "convertibles" fue dada por Little (1975) quien demostró que tales matrices son precisamente aquellas que son la matriz de biadjacencia de grafos bipartitos que tienen una orientación pfaffiana : una orientación de las aristas tal que para cada ciclo par para el cual${\displaystyle T}$${\displaystyle \operatorname {per} T(A)=\det A}$${\displaystyle n\times n}$${\displaystyle A}$${\displaystyle C}$${\displaystyle G\setminus C}$tiene una coincidencia perfecta, hay un número impar de bordes dirigidos a lo largo de C (y, por lo tanto, un número impar con la orientación opuesta). También se demostró que estos gráficos son exactamente aquellos que no contienen un subgrafo homeomorfo a , como el anterior.${\displaystyle K_{3,3}}$

Módulo de cálculo un número

Modulo 2, la permanente es el mismo que el determinante, como También se puede calcular de módulo en el tiempo para . Sin embargo, es UP-difícil calcular el módulo permanente cualquier número que no sea una potencia de 2. Valiant (1979)${\displaystyle (-1)\equiv 1{\pmod {2}}.}$${\displaystyle 2^{k}}$${\displaystyle O(n^{4k-3})}$${\displaystyle k\geq 2}$

Hay varias fórmulas dadas por Glynn (2010) para el cálculo módulo a primo p . Primero, hay uno que usa cálculos simbólicos con derivadas parciales.

En segundo lugar, para p = 3 existe la siguiente fórmula para una matriz n × n , que involucra a los principales menores de la matriz ( Kogan (1996) ): ${\displaystyle A}$

${\displaystyle \operatorname {per} (A)=(-1)^{n}\Sigma _{J\subseteq \{1,\dots ,n\}}\det(A_{J})\det(A_{\bar {J}}),}$

donde es la submatriz de inducida por las filas y columnas de indexado por , y es el complemento de in , mientras que el determinante de la submatriz vacía se define como 1.${\displaystyle A_{J}}$${\displaystyle A}$${\displaystyle A}$${\displaystyle J}$${\displaystyle {\bar {J}}}$${\displaystyle J}$${\displaystyle \{1,\dots ,n\}}$

La expansión anterior se puede generalizar en una característica arbitraria p como el siguiente par de identidades duales:

$${\displaystyle \operatorname {per} (A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\det(A_{J_{1}})\dots \det(A_{J_{p-1}})}$$

$${\displaystyle \det(A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\operatorname {per} (A_{J_{1}})\dots \operatorname {per} (A_{J_{p-1}})}$$

donde en ambas fórmulas la suma se toma sobre todas las tuplas (p-1) que son particiones del conjunto en subconjuntos p-1, algunas de ellas posiblemente vacías.${\displaystyle {J_{1}},...,{J_{p-1}}}$${\displaystyle \{1,\dots ,n\}}$

La primera fórmula posee un análogo para el hafniano de una p simétrica e impar:${\displaystyle A}$

$${\displaystyle \operatorname {haf} ^{2}(A)=(-1)^{n}\Sigma _{{J_{1}},...,{J_{p-1}}}\det(A_{J_{1}})\dots \det(A_{J_{p-1}})(-1)^{|J_{1}|+\dots +|J_{(p-1)/2}|}}$$

con la suma tomada sobre el mismo conjunto de índices. Además, en la característica cero, una expresión de suma de convolución similar que involucra tanto al determinante como al permanente produce el polinomio del ciclo hamiltoniano (definido como donde es el conjunto de n-permutaciones que tienen un solo ciclo):${\textstyle \operatorname {ham} (A)=\sum _{\sigma \in H_{n}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$${\displaystyle {H_{n}}}$

$${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {per} (A_{\bar {J}})(-1)^{|J|}.}$$

En la característica 2, la última igualdad se convierte en lo que, por lo tanto, brinda la oportunidad de calcular en tiempo polinómico el polinomio del ciclo hamiltoniano de cualquier unitario (es decir, tal que dónde está la identidad n × n -matriz), porque cada menor de dicha matriz coincide con su Complemento algebraico: donde es la identidad n × n -matriz con la entrada de los índices 1,1 reemplazada por 0. Además, puede, a su vez, generalizarse más para una matriz unitaria n × n como donde es un subconjunto de { 1,…, n },${\displaystyle \operatorname {ham} (A)=\Sigma _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$ ${\displaystyle U}$${\displaystyle U^{T}U=I}$${\displaystyle I}$${\displaystyle \operatorname {ham} (U)=\operatorname {det} ^{2}(U+I_{/1})}$${\displaystyle I_{/1}}$ ${\displaystyle U}$${\displaystyle \operatorname {ham_{K}} (U)={\det }^{2}(U+I_{/K})}$${\displaystyle K}$${\displaystyle I_{/K}}$es la identidad n × n -matriz con las entradas de los índices k , k reemplazado por 0 para todos los k pertenecientes a , y definimos donde es el conjunto de n-permutaciones cuyo cada ciclo contiene al menos un elemento de .${\displaystyle K}$${\textstyle \operatorname {ham_{K}} (A)=\sum _{\sigma \in H_{n}{(K)}}\prod _{i=1}^{n}a_{i,\sigma (i)}}$${\displaystyle {H_{n}{(K)}}}$${\displaystyle K}$

Esta fórmula también implica las siguientes identidades en los campos de la característica 3:

para cualquier invertible ${\displaystyle A}$

${\displaystyle \operatorname {per} (A^{-1}){\det }^{2}(A)=\operatorname {per} (A);}$

para cualquier unitario , es decir, una matriz cuadrada tal que donde está la matriz identidad del tamaño correspondiente,${\displaystyle U}$${\displaystyle U}$${\displaystyle U^{T}U=I}$${\displaystyle I}$

${\displaystyle \operatorname {per} ^{2}(U)=\det(U+V)\det(-U)}$

donde es la matriz cuyas entradas son los cubos de las entradas correspondientes de .${\displaystyle V}$${\displaystyle U}$

También se demostró ( Kogan (1996) ) que, si definimos una matriz cuadrada como k-semi-unitaria cuando , la permanente de una matriz 1-semi-unitaria es computable en tiempo polinomial sobre campos de característica 3, mientras que para k > 1 el problema pasa a ser # 3-P-complete . (Una teoría paralela concierne al polinomio del ciclo hamiltoniano en la característica 2: mientras que calcularlo en las matrices unitarias es factible en tiempo polinómico, el problema es # 2-P-completo para los k-semi-unitarios para cualquier k > 0). Este último resultado se amplió esencialmente en 2017 ( Knezevic & Cohen (2017)${\displaystyle A}$${\displaystyle \operatorname {rank} (A^{T}A-I)=k}$) Y se comprobó que en la característica 3 existe una fórmula simple relativa de los permanentes de una matriz cuadrada y su inverso parcial (por y ser cuadrado, siendo invertible ):${\displaystyle A_{11}}$${\displaystyle A_{22}}$${\displaystyle A_{11}}$

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}={\det }^{2}\left(A_{11}\right)\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}}$$

y permite reducir en tiempo polinomial el cálculo de la permanente de una matriz n × n con un subconjunto de k o k −1 filas expresables como combinaciones lineales de otro subconjunto (disjunto) de k filas al cálculo de la permanente de una ( n - k ) × ( n - k ) - o ( n - k +1) × ( n - k +1) -matriz correspondientemente, habiendo introducido un operador de compresión (análogo a la modificación gaussiana aplicada para calcular el determinante ) que "conserva" lo permanente en la característica 3. (De manera análoga, cabe señalar que laEl polinomio de ciclo hamiltoniano en la característica 2 también posee sus compresiones matriciales invariantes, teniendo en cuenta el hecho de que ham ( A ) = 0 para cualquier matriz A n × n que tenga tres filas iguales o, si n > 2, un par de índices i , j tales que sus filas i -ésima y j -ésima son idénticas y sus i -ésima y j-th columnas son idénticas también.) El cierre de ese operador definido como el límite de su aplicación secuencial junto con la transformación de transposición (utilizada cada vez que el operador deja la matriz intacta) también es un mapeo de operador, cuando se aplica a clases de matrices, una clase a otra. Mientras que el operador de compresión mapea la clase de matrices 1-semi-unitarias a sí mismo y las clases de matrices unitarias y 2-semi-unitarias, el cierre de compresión de la clase 1-semi-unitaria (así como la clase de matrices recibidas de unitariounos mediante la sustitución de una fila por un vector de fila arbitrario (el permanente de dicha matriz es, a través de la expansión de Laplace, la suma de los permanentes de matrices 1-semi-unitarias y, en consecuencia, polinomial-tiempo computable) es aún desconocido y tensamente relacionado con el problema general de la complejidad computacional de la permanente en la característica 3 y la pregunta principal de P versus NP : como se mostró en ( Knezevic y Cohen (2017) ), si tal cierre de compresión es el conjunto de todas las matrices cuadradas sobre un campo de característica 3 o, al menos, contiene una clase de matriz en la que el cálculo del permanente es # 3-P-completo (como la clase de matrices 2-semi-unitarias), entonces el permanente es computable en tiempo polinómico en esta característica.

Además, se formuló el problema de encontrar y clasificar posibles análogos de las compresiones de preservación permanente existentes en la característica 3 para otras características primarias ( Knezevic & Cohen (2017) ), dando la siguiente identidad para una matriz n × n y dos n -vectores (que tienen todas sus entradas del conjunto {0,…, p −1}) y tales que , válidos en una característica prima arbitraria p :${\displaystyle A}$${\displaystyle \alpha }$${\displaystyle \beta }$${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$

$${\displaystyle \operatorname {per} (A^{\left(\alpha ,\beta \right)})={\det }^{p-1}(A)\operatorname {per} \left(A^{-1}\right)^{\left(\left(p-1\right){\vec {1}}_{n}-\beta ,\left(p-1\right){\vec {1}}_{n}-\alpha \right)}\left(\prod _{i=1}^{n}\alpha _{i}!\right)\left(\prod _{j=1}^{n}\beta _{j}!\right)\left(-1\right)^{n+\sum _{i=1}^{n}\alpha _{i}}}$$

donde para una matriz n × m , un vector n y un vector m , ambos vectores que tienen todas sus entradas del conjunto {0,…, p −1}, denota la matriz recibida a través de la repetición de veces su i -ésima fila para i = 1, ..., n y veces su j columna -ésima para j = 1, ..., m (si algunos iguales multiplicidad de columna de fila o cero significaría que se eliminó la fila o columna, y por lo tanto esta noción es una generalización de la noción de submatriz), y${\displaystyle M}$${\displaystyle x}$${\displaystyle y}$${\displaystyle M^{(x,y)}}$${\displaystyle M}$${\displaystyle x_{i}}$${\displaystyle y_{j}}$${\displaystyle {\vec {1}}_{n}}$denota el vector n todas cuyas entradas son iguales a la unidad. Esta identidad es una analogía exacta de la fórmula clásica que expresa la menor de una matriz a través de una menor de su inversa y, por lo tanto, demuestra (una vez más) una especie de dualidad entre lo determinante y lo permanente como inmanentes relativos. (En realidad, su propio análogo para el hafniano de un primo p simétrico e impar es ).${\displaystyle A}$${\textstyle \operatorname {haf} ^{2}(A^{\left(\alpha ,\alpha \right)})=\det ^{p-1}(A)\operatorname {haf} ^{2}\left(A^{-1}\right)^{\left((p-1\right){\vec {1}}_{n}-\alpha ,\left(p-1\right){\vec {1}}_{n}-\alpha )}(\prod _{i=1}^{n}\alpha _{i}!)^{2}(-1)^{n(p-1)/2+n+\sum _{i=1}^{n}\alpha _{i}}}$

Y, como una generalización aún más amplia para el caso inverso parcial en una característica primo p, para , siendo cuadrada, siendo invertible y del tamaño de x , y , allí también mantiene la identidad${\displaystyle A_{11}}$${\displaystyle A_{22}}$${\displaystyle A_{11}}$${\displaystyle {n_{1}}}$${\displaystyle {n_{1}}}$${\textstyle {\sum _{i=1}^{n}\alpha _{i}=\sum _{j=1}^{n}\beta _{j}}}$

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}^{\left(\alpha ,\beta \right)}={\det }^{p-1}(A_{11})\operatorname {per} {\begin{pmatrix}A_{11}^{-1}&A_{11}^{-1}A_{12}\\A_{21}A_{11}^{-1}&A_{22}-A_{21}A_{11}^{-1}A_{12}\end{pmatrix}}^{\left(\left(p-1\right){\vec {1}}_{n}-\beta ,\left(p-1\right){\vec {1}}_{n}-\alpha \right)}\left(\prod _{i=1}^{n}\alpha _{1,i}!\right)\left(\prod _{j=1}^{n}\beta _{1,j}!\right)\left(-1\right)^{n_{1}+\sum _{i=1}^{n}\alpha _{1,i}}}$$

donde los vectores de multiplicidad de filas / columnas comunes y para la matriz generan los vectores de multiplicidad de filas / columnas correspondientes y , s, t = 1,2, para sus bloques (lo mismo ocurre con el inverso parcial en el lado derecho de la igualdad).${\displaystyle \alpha }$${\displaystyle \beta }$${\displaystyle A}$${\displaystyle \alpha _{s}}$${\displaystyle \beta _{t}}$${\displaystyle A}$

Cálculo aproximado

Cuando las entradas de A son no negativas, la permanente se puede calcular aproximadamente en tiempo polinomial probabilístico , hasta un error de ε M , donde M es el valor de la permanente y ε> 0 es arbitrario. En otras palabras, existe un esquema de aproximación aleatorizado en tiempo polinómico (FPRAS) ( Jerrum, Vigoda y Sinclair (2001) ). harvtxt error: no target: CITEREFJerrumVigodaSinclair2001 (help)

El paso más difícil en el cálculo es la construcción de un algoritmo para muestrear casi uniformemente del conjunto de todos los emparejamientos perfectos en un gráfico bipartito dado: en otras palabras, un muestreador casi uniforme completamente polinomial (FPAUS). Esto se puede hacer usando un algoritmo de Monte Carlo de cadena de Markov que usa una regla de Metropolis para definir y ejecutar una cadena de Markov cuya distribución es casi uniforme y cuyo tiempo de mezcla es polinomial.

Es posible contar aproximadamente el número de emparejamientos perfectos en un gráfico a través de la autorreductibilidad del permanente, utilizando el FPAUS en combinación con una reducción bien conocida del muestreo al conteo debido a Jerrum, Valiant & Vazirani (1986) . Dejar que denotan el número de apareamientos perfectos en . Aproximadamente, para cualquier ventaja en particular , muestreando muchas coincidencias y contando cuántas de ellas son coincidencias , se puede obtener una estimación de la proporción . El número es entonces , donde se puede aproximar aplicando el mismo método de forma recursiva. harvtxt error: no target: CITEREFJerrumValiantVazirani1986 (help)${\displaystyle M(G)}$${\displaystyle G}$${\displaystyle e}$${\displaystyle G}$${\displaystyle G}$${\displaystyle G\setminus e}$${\textstyle \rho ={\frac {M(G)}{M(G\setminus e)}}}$${\displaystyle M(G)}$${\displaystyle \rho M(G\setminus e)}$${\displaystyle M(G\setminus e)}$

Otra clase de matrices para las que se puede calcular aproximadamente la permanente es el conjunto de matrices semidefinidas positivas (el problema de la teoría de la complejidad de aproximar la permanente de tales matrices dentro de un error multiplicativo se considera abierto ^[7] ). El correspondiente algoritmo aleatorizado se basa en el modelo de muestreo de bosones y utiliza las herramientas propias de la óptica cuántica , para representar el permanente de matrices positivas-semidefinidas como el valor esperado de una determinada variable aleatoria. A continuación, este último se aproxima por su media muestral. ^[8]Este algoritmo, para un cierto conjunto de matrices semidefinidas positivas, aproxima su tiempo permanente en polinomio hasta un error aditivo, que es más confiable que el del algoritmo clásico estándar de tiempo polinomial de Gurvits. ^[9]

Notas

1. A partir de 2008, consulte Rempala y Wesolowski (2008) harvtxt error: no target: CITEREFRempalaWesolowski2008 (help)
2. van Lint y Wilson (2001) p. 99
3. Enciclopedia Concisa de Matemáticas CRC harvtxt error: no target: CITEREFCRC_Concise_Encyclopedia_of_Mathematics (help)
4. Nijenhuis y Wilf (1978)
5. Pequeño (1974) , Vazirani (1988)
6. Pólya (1913) , Reich (1971)
7. Vea el problema abierto (4) en "Shtetl Optimized: Presentando a algunos británicos a P vs. NP" .
8. Chakhmakhchyan, Levon; Cerf, Nicolas; García-Patrón, Raúl (2017). "Un algoritmo de inspiración cuántica para estimar la permanente de matrices semidefinidas positivas". Phys. Rev. A . 96 (2): 022329. arXiv : 1609.02416 . Código bibliográfico : 2017PhRvA..96b2329C . doi : 10.1103 / PhysRevA.96.022329 . S2CID 54194194 . 
9. Gurvits, Leonid (2005). "Sobre la complejidad de los discriminantes mixtos y problemas relacionados". Fundamentos matemáticos de la informática . Apuntes de conferencias en Ciencias de la Computación. 3618 : 447–458. doi : 10.1007 / 11549345_39 . ISBN 978-3-540-28702-5.

Referencias

• Allender, Eric; Gore, Vivec (1994), "Un circuito uniforme límite inferior para lo permanente", SIAM Journal on Computing , 23 (5): 1026–1049, CiteSeerX  10.1.1.51.3546 , doi : 10.1137 / s0097539792233907

• Balasubramanian, K. (1980), Combinatoria y diagonales de matrices (PDF) , Ph.D. Tesis, Departamento de Estadística, Loyola College, Madrás, India, T073 , Instituto Indio de Estadística, Calcuta

• Bax, Eric (1998), Algoritmos de diferencias finitas para problemas de conteo , Ph.D. Disertación, 223 , Instituto de Tecnología de California

• Bax, Eric; Franklin, J. (1996), Un tamiz de diferencias finitas para calcular el permanente , Caltech-CS-TR-96-04, Instituto de Tecnología de California

• Glynn, David G. (2010), "La permanente de una matriz cuadrada", European Journal of Combinatorics , 31 (7): 1887–1891, doi : 10.1016 / j.ejc.2010.01.010

• Glynn, David G. (2013), "Fórmulas permanentes de Veronesean", Diseños, códigos y criptografía , 68 (1–3): 39–47, doi : 10.1007 / s10623-012-9618-1 , S2CID  36911503

• Jerrum, M .; Sinclair, A .; Vigoda, E. (2001), "Un algoritmo de aproximación polinomial-temporal para el permanente de una matriz con entradas no negativas", Proc. 33º Simposio de Teoría de la Computación , págs. 712–721, doi : 10.1145 / 380752.380877 , ISBN 978-1581133493, S2CID  8368245 , ECCC  TR00-079
• Mark Jerrum ; Leslie Valiant ; Vijay Vazirani (1986), "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme", Informática teórica , 43 : 169-188, doi : 10.1016 / 0304-3975 (86) 90174-X

• Kogan, Grigoriy (1996), "Computación permanente sobre campos de característica 3: dónde y por qué se vuelve difícil", 37º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (FOCS '96) : 108-114, doi : 10.1109 / SFCS.1996.548469 , ISBN 0-8186-7594-2, S2CID  39024286

• Knezevic, Anna; Cohen, Greg (2017), Algunos hechos sobre permanentes en características finitas , arXiv : 1710.01783 , Bibcode : 2017arXiv171001783K

• van Lint, Jacobus Hendricus; Wilson, Richard Michale (2001), Un curso de combinatoria , ISBN 978-0-521-00601-9

• Little, CHC (1974), "Una extensión del método de Kasteleyn de enumerar los factores 1 de gráficos planos", en Holton, D. (ed.), Proc. Segunda Conf. Australiana Matemáticas combinatorias , Lecture Notes in Mathematics, 403 , Springer-Verlag, págs. 63–72

• Little, CHC (1975), "Una caracterización de matrices convertibles (0, 1)", Journal of Combinatorial Theory , Serie B, 18 (3): 187-208, doi : 10.1016 / 0095-8956 (75) 90048- 9

• Marcus, M .; Minc, H. (1961), "Sobre la relación entre lo determinante y lo permanente", Illinois Journal of Mathematics , 5 (3): 376–381, doi : 10.1215 / ijm / 1255630882

• Nijenhuis, Albert; Wilf, Herbert S. (1978), algoritmos combinatorios , Academic Press

• Pólya, G. (1913), "Aufgabe 424", Arch. Matemáticas. Phys. , 20 (3): 27

• Reich, Simeon (1971), "Otra solución de un viejo problema de pólya", American Mathematical Monthly , 78 (6): 649–650, doi : 10.2307 / 2316574 , JSTOR  2316574

• Rempała, Grzegorz A .; Wesolowski, Jacek (2008), Funcionales simétricos en matrices aleatorias y problemas de emparejamientos aleatorios , pág. 4, ISBN 978-0-387-75145-0

• Ryser, Herbert John (1963), Matemáticas combinatorias , The Carus Mathematical Monographs, vol. 14, Asociación Matemática de América

• Vazirani, Vijay V. (1988), "Algoritmos NC para calcular el número de emparejamientos perfectos en gráficos libres de K _3,3 y problemas relacionados", Proc. 1er Taller escandinavo sobre teoría de algoritmos (SWAT '88) , Lecture Notes in Computer Science, 318 , Springer-Verlag, págs. 233–242, doi : 10.1007 / 3-540-19487-8_27 , hdl : 1813/6700 , ISBN 978-3-540-19487-3

• Valiant, Leslie G. (1979), "La complejidad de calcular lo permanente", Informática teórica , Elsevier, 8 (2): 189-201, doi : 10.1016 / 0304-3975 (79) 90044-6

• "Permanente", CRC Concise Encyclopedia of Mathematics , Chapman & Hall / CRC, 2002

Otras lecturas

• Barvinok, A. (2017), "Aproximación de permanentes y hafnianos", Análisis discreto , arXiv : 1601.07518 , doi : 10.19086 / da.1244 , S2CID  397350.