Calculando el permanente

Problema de álgebra lineal

En álgebra lineal , el cálculo de la permanente de una matriz es un problema que se considera 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 elementos de la matriz que se encuentran en filas y columnas distintas. Sin embargo, mientras que el determinante pondera cada uno de estos productos con un signo ±1 en función de la paridad del conjunto , el permanente los pondera a todos con un signo +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 del 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 circuitos ACC ^{0 uniformes en el espacio logarítmico. (Allender y 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

La 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 se extiende aquí 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 difiere 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 se puede traducir directamente a un algoritmo que expande 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 puede darse ^[2] de la siguiente manera: Sea obtenido a partir de A eliminando k columnas, sea el producto de las sumas de filas de , y sea la suma de los valores de sobre todos los posibles . Entonces ${\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 orden de 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 de rápida) se encuentra en las dos tesis doctorales; véase (Balasubramanian 1980), (Bax 1998); también (Bax y Franklin 1996). Los métodos para encontrar la fórmula son bastante diferentes, y 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 de invariantes, es a través de la identidad de polarización para un tensor simétrico (Glynn 2010). La fórmula se generaliza a una infinidad de otras, como las encontradas por todos estos autores, aunque no está claro si son más rápidas que la básica. Véase (Glynn 2013).

La fórmula más simple conocida 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 exterior es 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 yK3,3-gratis

El número de emparejamientos perfectos en un grafo bipartito se cuenta por la permanente de la matriz de biyacencia del grafo , y la permanente de cualquier matriz 0-1 se puede interpretar de esta manera como el número de emparejamientos perfectos en un grafo. Para grafos planares (independientemente de la bipartididad), el algoritmo FKT calcula el número de emparejamientos perfectos en tiempo polinomial cambiando los signos de un subconjunto cuidadosamente elegido de las entradas en la matriz de Tutte del grafo, de modo que el Pfaffian de la matriz antisimétrica resultante (la raíz cuadrada de su determinante ) sea el número de emparejamientos perfectos. Esta técnica se puede generalizar a grafos que no contienen ningún subgrafo homeomorfo al grafo bipartito completo K _3,3 . ^[5]

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

Cálculo módulo un número

Módulo 2, el permanente es lo mismo que el determinante, ya que también se puede calcular módulo en el tiempo para . Sin embargo, es UP-difícil calcular el permanente módulo 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}$

Existen varias fórmulas dadas por Glynn (2010) para el cálculo del módulo de un primo p . En primer lugar, hay una que utiliza 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 los menores principales de la matriz (Kogan (1996)): ${\displaystyle A}$

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

donde es la submatriz de inducida por las filas y columnas de indexadas por , y es el complemento de en , 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: donde en ambas fórmulas la suma se toma sobre todas las ( p − 1)-tuplas que son particiones del conjunto en p − 1 subconjuntos, algunos de ellos posiblemente vacíos. $${\displaystyle {\begin{aligned}\operatorname {per} (A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \det(A_{J_{p-1}})\\\det(A)&=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\operatorname {per} (A_{J_{1}})\dotsm \operatorname {per} (A_{J_{p-1}})\end{aligned}}}$$ ${\displaystyle {J_{1}},\ldots ,{J_{p-1}}}$ ${\displaystyle \{1,\dots ,n\}}$

La fórmula anterior posee un análogo para el hafniano de un p simétrico y uno impar: ${\displaystyle A}$

$${\displaystyle \operatorname {haf} ^{2}(A)=(-1)^{n}\sum _{{J_{1}},\ldots ,{J_{p-1}}}\det(A_{J_{1}})\dotsm \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 permanente como al determinante produce el polinomio de ciclo hamiltoniano (definido como donde es el conjunto de n-permutaciones que tienen solo un 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)=\sum _{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 proporciona una oportunidad para calcular en tiempo polinomial el polinomio del ciclo hamiltoniano de cualquier unitario (es decir, tal que donde es la matriz identidad n × n ), porque cada menor de dicha matriz coincide con su complemento algebraico: donde es la matriz identidad n × n con la entrada de índices 1,1 reemplazada por 0. Además, puede, a su vez, generalizarse aún más para una matriz unitaria n × n como donde es un subconjunto de {1, ..., n }, es la matriz identidad n × n con las entradas de índices k , k reemplazadas 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 \operatorname {ham} (A)=\sum _{J\subseteq \{2,\dots ,n\}}\det(A_{J})\operatorname {det} (A_{\bar {J}})}$ ${\displaystyle U}$ ${\displaystyle U^{\textsf {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)=\operatorname {det} ^{2}(U+I_{/K})}$ ${\displaystyle K}$ ${\displaystyle I_{/K}}$ ${\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 sobre campos de característica 3:

Para cualquier invertible ${\displaystyle A}$

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

para cualquier matriz unitaria , es decir, cuadrada, tal que donde es la matriz identidad del tamaño correspondiente, ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle U^{\textsf {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 ha demostrado (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 cuerpos de característica 3, mientras que para k > 1 el problema se convierte en #3-P-completo . (Una teoría paralela se refiere al polinomio del ciclo hamiltoniano en la característica 2: mientras que calcularlo sobre las matrices unitarias es factible en tiempo polinomial, el problema es #2-P-completo para las k-semi-unitarias para cualquier k > 0). El último resultado se extendió esencialmente en 2017 (Knezevic & Cohen (2017)) y se demostró que en la característica 3 hay una fórmula simple que relaciona las permanentes de una matriz cuadrada y su inversa parcial (para y siendo cuadradas, siendo invertibles ): ${\displaystyle A}$ ${\displaystyle \operatorname {rank} (A^{\textsf {T}}A-I)=k}$ ${\displaystyle A_{11}}$ ${\displaystyle A_{22}}$ ${\displaystyle A_{11}}$

$${\displaystyle \operatorname {per} {\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}}=\operatorname {det} ^{2}(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}}}$$

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 matriz ( n − k )×( n − k )- o ( n − k + 1)×( n − k + 1)- correspondientemente, habiendo introducido por tanto un operador de compresión (análogo a la modificación gaussiana aplicada para calcular el determinante) que "preserva" la permanente en la característica 3. (Analógicamente, valdría la pena notar que el 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 n × n A 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 columnas i -ésima y j -ésima también son idénticas.) 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) es también un operador que mapea, cuando se aplica a clases de matrices, una clase a otra. Mientras que el operador de compresión mapea la clase de matrices 1-semiunitarias a sí misma y a las clases de matrices unitarias y 2-semiunitarias, el cierre de compresión de la clase 1-semiunitaria (así como la clase de matrices recibidas de matrices unitarias al reemplazar una fila por un vector de fila arbitrario —la permanente de tal matriz es, a través de la expansión de Laplace, la suma de las permanentes de matrices 1-semiunitarias y, en consecuencia, computable en tiempo polinomial) es aún desconocida y está tensamente relacionada 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 & Cohen (2017)), si tal cierre de compresión es el conjunto de todas las matrices cuadradas sobre un cuerpo de característica 3 o, al menos, contiene una clase de matriz sobre la cual el cálculo de la permanente es #3-P-completo (como la clase de matrices 2-semiunitarias), entonces la permanente es computable en tiempo polinomial en esta característica.

Además, se formuló el problema de encontrar y clasificar cualquier análogo posible de las compresiones de conservación permanente existentes en la característica 3 para otras características primos (Knezevic y Cohen (2017)), al tiempo que se daba la siguiente identidad para una matriz n × n y dos n -vectores (que tienen todas sus entradas del conjunto {0, ..., p − 1}) y tal que , válida en una característica primo 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^{(\alpha ,\beta )})=\det ^{p-1}(A)\operatorname {per} (A^{-1})^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)\left(\prod _{j=1}^{n}\beta _{j}!\right)(-1)^{n+\sum _{i=1}^{n}\alpha _{i}}}$$

donde para una matriz n × m , un vector n y un vector m , ambos vectores teniendo todas sus entradas del conjunto {0, ..., p − 1}, denota la matriz recibida de mediante la repetición de veces su i -ésima fila para i = 1, ..., n y de veces su j -ésima columna para j = 1, ..., m (si la multiplicidad de alguna fila o columna es igual a cero significaría que la fila o columna fue eliminada, y por lo tanto esta noción es una generalización de la noción de submatriz), y denota el vector n cuyas entradas son todas iguales a la unidad. Esta identidad es un análogo exacto de la fórmula clásica que expresa el menor de una matriz a través de un menor de su inversa y por lo tanto demuestra (una vez más) una especie de dualidad entre el determinante y el permanente como inmanentes relativos. (En realidad su propio análogo para el hafniano de un primo simétrico e impar p es ). ${\displaystyle M}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M^{(x,y)}}$ ${\displaystyle M}$ ${\displaystyle x_{i}}$ ${\displaystyle y_{j}}$ ${\displaystyle {\vec {1}}_{n}}$ ${\displaystyle A}$ ${\textstyle \operatorname {haf} ^{2}(A^{(\alpha ,\alpha )})=\det ^{p-1}(A)\operatorname {haf} ^{2}(A^{-1})^{((p-1){\vec {1}}_{n}-\alpha ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{i}!\right)^{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 prima p, para , siendo cuadrado, invertible y de tamaño x , y , se cumple también 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}}^{(\alpha ,\beta )}={\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}}^{((p-1){\vec {1}}_{n}-\beta ,(p-1){\vec {1}}_{n}-\alpha )}\left(\prod _{i=1}^{n}\alpha _{1,i}!\right)\left(\prod _{j=1}^{n}\beta _{1,j}!\right)(-1)^{n_{1}+\sum _{i=1}^{n}\alpha _{1,i}}}$$

donde los vectores de multiplicidad de fila/columna comunes y para la matriz generan los vectores de multiplicidad de fila/columna correspondientes y , s,t = 1,2, para sus bloques (lo mismo se aplica a la inversa parcial de 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 no son negativas, el permanente se puede calcular de manera aproximada en tiempo polinomial probabilístico , hasta un error de ε M , donde M es el valor del permanente y ε > 0 es arbitrario. En otras palabras, existe un esquema de aproximación aleatoria en tiempo polinomial (FPRAS) completamente aleatorio (Jerrum, Sinclair y Vigoda (2001)).

El paso más difícil del cálculo es la construcción de un algoritmo para muestrear de manera casi uniforme el conjunto de todas las coincidencias perfectas en un grafo bipartito dado: en otras palabras, un muestreador casi uniforme completamente polinomial (FPAUS). Esto se puede hacer utilizando un algoritmo de Monte Carlo de cadena de Markov que utiliza una regla de Metropolis para definir y ejecutar una cadena de Markov cuya distribución sea casi uniforme y cuyo tiempo de mezcla sea polinomial.

Es posible contar aproximadamente el número de emparejamientos perfectos en un grafo a través de la auto-reducibilidad de la permanente, utilizando el FPAUS en combinación con una reducción bien conocida de muestreo a conteo debido a Jerrum, Valiant y Vazirani (1986). Sea el número de emparejamientos perfectos en . Aproximadamente, para cualquier borde particular en , al muestrear muchos emparejamientos en y contar cuántos de ellos son emparejamientos en , se puede obtener una estimación de la razón . El número es entonces , donde se puede aproximar aplicando el mismo método de forma recursiva. ${\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 la permanente es de particular interés son las matrices semidefinidas positivas . ^[7] Utilizando una técnica de conteo de Stockmeyer, se pueden calcular dentro de la clase , pero esta se considera una clase inviable en general. Es NP-difícil aproximar permanentes de matrices PSD dentro de un factor subexponencial, y se conjetura que es -difícil ^[8] Si se imponen más restricciones al espectro , se conocen algoritmos más eficientes. Un algoritmo aleatorio se basa en el modelo de muestreo de bosones y utiliza las herramientas propias de la óptica cuántica para representar la permanente de matrices semidefinidas positivas como el valor esperado de una variable aleatoria específica. Esta última se aproxima luego por su media muestral. ^[9] Este algoritmo, para un cierto conjunto de matrices semidefinidas positivas, aproxima su permanente en tiempo polinomial hasta un error aditivo, que es más confiable que el del algoritmo clásico estándar de tiempo polinomial de Gurvits. ^[10] ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$ ${\displaystyle {\textsf {BPP}}^{\textsf {NP}}}$

Notas

1. A partir de 2008, véase Rempała y Wesolowski (2008)
2. van Lint y Wilson (2001) pág. 99
3. Enciclopedia concisa de matemáticas CRC
4. Nijenhuis y Wilf (1978)
5. Pequeño (1974), Vazirani (1988)
6. Polya (1913), Reich (1971)
7. Véase el problema abierto (4) en Shtetl Optimized: Introducing some British people to P vs. NP, 22 de julio de 2015
8. Meiburg, Alexander (2023), "Inaproximabilidad de permanentes semidefinidos positivos y tomografía de estados cuánticos", Algorithmica , 85 (12): 3828–3854, arXiv : 2111.03142 , doi : 10.1007/s00453-023-01169-1
9. Chakhmakhchyan, Levon; Cerf, Nicolas; Garcia-Patron, Raul (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 , Bibcode :2017PhRvA..96b2329C, doi :10.1103/PhysRevA.96.022329, S2CID  54194194
10. Gurvits, Leonid (2005), "Sobre la complejidad de los discriminantes mixtos y problemas relacionados", Fundamentos matemáticos de la informática 2005 , Lecture Notes in Computer Science, vol. 3618, págs. 447–458, doi :10.1007/11549345_39, ISBN 978-3-540-28702-5

Referencias

• Allender, Eric; Gore, Vivec (1994), "Un límite inferior de circuito uniforme para el 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) , tesis doctoral, Departamento de Estadística, Loyola College, Madrás, India, vol. T073, Instituto de Estadística de la India, Calcuta
• Bax, Eric (1998), Algoritmos de diferencias finitas para problemas de conteo , Tesis doctoral, vol. 223, Instituto Tecnológico de California
• Bax, Eric; Franklin, J. (1996), Un tamiz de diferencias finitas para calcular la , Caltech-CS-TR-96-04, Instituto Tecnológico 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 del Veronese", 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 en tiempo polinomial para la permanente de una matriz con entradas no negativas", Proc. 33.° Simposio sobre teoría de la computación , págs. 712–721, doi :10.1145/380752.380877, ISBN 978-1581133493, S2CID  8368245, ECCC  TR00-079
• Jerrum, Mark ; Valiant, Leslie ; Vazirani, Vijay (1986), "Generación aleatoria de estructuras combinatorias a partir de una distribución uniforme", Theoretical Computer Science , 43 : 169–188, doi :10.1016/0304-3975(86)90174-X
• Kogan, Grigoriy (1996), "Cálculo de permanentes sobre campos de característica 3: dónde y por qué resulta difícil", Actas de la 37.ª Conferencia sobre Fundamentos de la Ciencia de la Computación , págs. 108-114, doi :10.1109/SFCS.1996.548469, ISBN 0-8186-7594-2, Número de identificación del sujeto  39024286
• Knezevic, Anna; Cohen, Greg (2017), Algunos datos sobre los permanentes en características finitas , arXiv : 1710.01783 , Bibcode :2017arXiv171001783K
• van Lint, Jacobus Hendricus; Wilson, Richard Michale (2001), Un curso de combinatoria , Cambridge University Press, ISBN 978-0-521-00601-9
• Little, CHC (1974), "Una extensión del método de Kasteleyn para enumerar los factores 1 de los grafos planares", en Holton, D. (ed.), Proc. 2nd Australian Conf. Combinatorial Mathematics , Lecture Notes in Mathematics, vol. 403, Springer-Verlag, págs. 63–72
• Little, CHC (1975), "Una caracterización de matrices (0, 1) convertibles", 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 el determinante y el 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. Math. 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 sobre matrices aleatorias y problemas de coincidencias aleatorias , Springer, p. 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 , ISBN 978-1-61444-014-7
• Vazirani, Vijay V. (1988), "Algoritmos NC para calcular el número de emparejamientos perfectos en grafos libres de K _{3,3 y problemas relacionados",} Proc. 1st Scandinavian Workshop on Algorithm Theory (SWAT '88) , Lecture Notes in Computer Science, vol. 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", Theoretical Computer Science , 8 (2), Elsevier: 189–201, doi :10.1016/0304-3975(79)90044-6, S2CID  1637832
• "Permanente", Enciclopedia concisa de matemáticas de la CRC , Chapman & Hall/CRC, 2002

Lectura adicional

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