♯P-completitud de 01-permanente

Una propiedad útil de${\displaystyle G_{\phi }}$es que sus ciclos cubren las asignaciones de variables para${\displaystyle \phi }$Para una funda de bicicleta${\displaystyle Z}$de${\displaystyle G_{\phi }}$, se puede decir que${\displaystyle Z}$induce una asignación de valores para las variables en${\displaystyle \phi }$por si acaso${\displaystyle Z}$contiene todos los bordes externos en${\displaystyle x_{i}}$El ciclo T de y ninguno de los bordes externos en${\displaystyle x_{i}}$Ciclo F para todas las variables${\displaystyle x_{i}}$que la asignación hace verdadera, y viceversa para todas las variables.${\displaystyle x_{i}}$que la asignación hace falso. Aunque cualquier ciclo dado cubre${\displaystyle Z}$no es necesario inducir una asignación para${\displaystyle \phi }$, cualquiera que lo haga induce exactamente una asignación, y la misma asignación inducida depende solo de los bordes externos de${\displaystyle Z}$. El término${\displaystyle Z}$se considera una cobertura de ciclo incompleta en esta etapa, porque solo se habla de sus bordes externos,${\displaystyle M}$En la sección siguiente se considera:${\displaystyle M}$-completaciones para demostrar que se tiene un conjunto de cubiertas de ciclo correspondientes a cada una${\displaystyle M}$que tengan las propiedades necesarias.

El tipo de portadas${\displaystyle Z}$que no inducen asignaciones son aquellas con ciclos que "salta" dentro de los componentes de la cláusula. Es decir, si para cada${\displaystyle C_{j}}$, al menos uno de${\displaystyle C_{j}}$Los bordes de entrada de están en${\displaystyle Z}$y cada borde de salida de los componentes de la cláusula está en${\displaystyle Z}$cuando el borde de entrada correspondiente está en${\displaystyle Z}$, entonces${\displaystyle Z}$es apropiado con respecto a cada componente de la cláusula, y${\displaystyle Z}$producirá una tarea satisfactoria para${\displaystyle \phi }$Esto se debe a que las cubiertas adecuadas${\displaystyle Z}$contienen el ciclo T completo o el ciclo F completo de cada variable.${\displaystyle x_{i}}$en${\displaystyle \phi }$así como cada uno incluyendo aristas que entran y salen de cada componente de la cláusula. Por lo tanto, estas cubiertas asignan verdadero o falso (pero nunca ambos) a cada${\displaystyle x_{i}}$y asegurar que se cumpla cada cláusula. Además, los conjuntos de coberturas de ciclo correspondientes a todos ellos${\displaystyle Z}$tener peso${\displaystyle 12^{m}}$y cualquier otro${\displaystyle Z}$tiene peso${\displaystyle 0}$Las razones de esto dependen de la estructura de los componentes de la cláusula y se detallan a continuación.

Para comprender las propiedades relevantes de los componentes de la cláusula${\displaystyle C_{j}}$, se necesita la noción de una M-completación. Una cobertura de ciclo${\displaystyle Z}$induce una asignación satisfactoria solo si sus aristas externas satisfacen ciertas propiedades. Para cualquier cobertura de ciclo de${\displaystyle G_{\phi }}$, consideremos solo sus aristas externas, el subconjunto${\displaystyle M}$. Dejar${\displaystyle M}$un conjunto de aristas externas. Un conjunto de aristas internas.${\displaystyle L}$es un${\displaystyle M}$-completar por si acaso${\displaystyle M\cup L}$es una cubierta de ciclo de${\displaystyle G_{\phi }}$. Además, denotemos el conjunto de todos${\displaystyle M}$-completaciones por${\displaystyle L^{M}}$y el conjunto de todas las cubiertas de ciclo resultantes de${\displaystyle G_{\phi }}$por${\displaystyle Z^{M}}$.

Recuerde que la construcción de${\displaystyle G_{\phi }}$era tal que cada borde externo tenía un peso de 1, por lo que el peso de${\displaystyle Z^{M}}$, el ciclo cubre los resultados de cualquier${\displaystyle M}$, depende únicamente de los bordes internos involucrados. Añadimos aquí la premisa de que la construcción de los componentes de la cláusula es tal que la suma sobre posibles${\displaystyle M}$-completaciones del peso de las aristas internas en cada componente de la cláusula, donde${\displaystyle M}$es apropiado en relación con el componente de la cláusula, es 12. De lo contrario, el peso de los bordes internos es 0. Dado que hay${\displaystyle m}$componentes de cláusulas y la selección de conjuntos de aristas internas,${\displaystyle L}$, dentro de cada componente de cláusula es independiente de la selección de conjuntos de aristas internas en otros componentes de cláusula, por lo que se puede multiplicar todo para obtener el peso de${\displaystyle Z^{M}}$. Entonces, el peso de cada${\displaystyle Z^{M}}$, dónde${\displaystyle M}$induce una asignación satisfactoria, es${\displaystyle 12^{m}}$. Además, donde${\displaystyle M}$no induce una asignación satisfactoria,${\displaystyle M}$no es apropiado con respecto a algunos${\displaystyle C_{j}}$, por lo tanto, el producto de los pesos de los bordes internos en${\displaystyle Z^{M}}$será${\displaystyle 0}$.

El componente de cláusula es un grafo dirigido ponderado con 7 nodos, cuyas aristas tienen pesos y están dispuestos para producir las propiedades especificadas anteriormente, y se presenta en el Apéndice A de Ben-Dor y Halevi (1993). Nótese que las aristas internas aquí tienen pesos extraídos del conjunto.${\displaystyle \{-1,0,1,2,3\}}$; no todas las aristas tienen pesos de 0 a 1.

Finalmente, dado que la suma de pesos de todos los conjuntos de recubrimientos de ciclos que inducen cualquier asignación particular satisfactoria es${\displaystyle 12^{m}}$y la suma de los pesos de todos los demás conjuntos de cubiertas de ciclo es 0, uno tiene${\displaystyle \operatorname {Perm} (G_{\phi })=12^{m}\cdot (\#\phi )}$La siguiente sección reduce el cálculo${\displaystyle \operatorname {Perm} (G_{\phi })}$al permanente de una matriz 01.

Utilizando aritmética modular , convierta una matriz entera.${\displaystyle A}$en una matriz no negativa equivalente${\displaystyle A'}$para que la permanente de${\displaystyle A}$se puede calcular fácilmente a partir del permanente de${\displaystyle A'}$, de la siguiente manera:

Dejar${\displaystyle A}$frijol${\displaystyle n\times n}$matriz de enteros donde ninguna entrada tiene una magnitud mayor que${\displaystyle \mu }$.

• Calcular${\displaystyle Q=2\cdot n!\cdot \mu ^{n}+1}$. La elección de${\displaystyle Q}$Esto se debe a que${\displaystyle |\operatorname {Perm} (A)|\leq n!\cdot \mu ^{n}}$
• Calcular${\displaystyle A'=A\,{\bmod {\,}}Q}$
• Calcular${\displaystyle P=\operatorname {Perm} (A'){\bmod {Q}}}$
• Si${\displaystyle P<Q/2}$entonces Perm( A ) = P . De lo contrario${\displaystyle \operatorname {Perm} (A)=P-Q}$

La transformación de${\displaystyle A}$en${\displaystyle A'}$es polinomial en${\displaystyle n}$y${\displaystyle \log(\mu )}$, ya que el número de bits necesarios para representar${\displaystyle Q}$es polinomial en${\displaystyle n}$y${\displaystyle \log(\mu )}$

A continuación se muestra un ejemplo de la transformación y por qué funciona.

${\displaystyle A={\begin{bmatrix}2&-2\\-2&1\end{bmatrix}}}$

${\displaystyle \operatorname {Perm} (A)=2\cdot 1+(-2)\cdot (-2)=6.}$

Aquí,${\displaystyle n=2}$,${\displaystyle \mu =2}$, y${\displaystyle \mu ^{n}=4}$, entonces${\displaystyle Q=17}$. De este modo

${\displaystyle A'=A{\bmod {1}}7={\begin{bmatrix}2&15\\15&1\end{bmatrix}}.}$

Nótese que los elementos son no negativos debido a la aritmética modular. Es sencillo calcular el permanente.

${\displaystyle \operatorname {Perm} (A')=2\cdot 1+15\cdot 15=227}$

entonces${\displaystyle P=227{\bmod {1}}7=6}$. Entonces${\displaystyle P<Q/2}$, entonces${\displaystyle \operatorname {Perm} (A)=P=6.}$

Tenga en cuenta que cualquier número puede descomponerse en una suma de potencias de 2. Por ejemplo,

${\displaystyle 13=2^{3}+2^{2}+2^{0}}$

Este hecho se utiliza para convertir una matriz no negativa en una matriz equivalente cuyas entradas son todas potencias de 2. La reducción se puede expresar en términos de gráficas equivalentes a las matrices.

Dejar${\displaystyle G}$ser un${\displaystyle n}$-grafo dirigido ponderado de nodos con pesos no negativos, donde el peso más grande es${\displaystyle W}$Cada borde${\displaystyle e}$con peso${\displaystyle w}$se convierte en una arista equivalente con pesos en potencias de 2 de la siguiente manera:

${\displaystyle w=2^{x_{1}}+2^{x_{2}}+\cdots +2^{x_{r}}}$,${\displaystyle 0\leq x_{1}\leq x_{2}\leq \cdots \leq x_{r}\leq \log(w)}$

Esto se puede ver gráficamente en la Figura 1. El subgrafo que reemplaza la arista existente contiene${\displaystyle r}$nodos y${\displaystyle 3r}$bordes.

Para demostrar que esto produce un gráfico equivalente${\displaystyle G'}$que tiene el mismo permanente que el original, se debe mostrar la correspondencia entre las cubiertas del ciclo de${\displaystyle G}$y${\displaystyle G'}$.

Considere alguna cobertura de ciclo${\displaystyle R}$en${\displaystyle G}$.

• Si un borde${\displaystyle e}$no está en${\displaystyle R}$, entonces para cubrir todos los nodos en el nuevo subgrafo, se deben usar los bucles propios. Dado que todos los bucles propios tienen un peso de 1, el peso de las coberturas de ciclos en${\displaystyle R}$y${\displaystyle R'}$fósforo.
• Si${\displaystyle e}$está en${\displaystyle R}$, luego en todas las coberturas de ciclo correspondientes en${\displaystyle G'}$, debe haber un camino desde${\displaystyle u}$a${\displaystyle v}$, dónde${\displaystyle u}$y${\displaystyle v}$son los nodos de arista${\displaystyle e}$. Desde la construcción, se puede ver que hay${\displaystyle r}$diferentes caminos y la suma de todos estos caminos es igual al peso de la arista en el grafo original.${\displaystyle G}$. Por lo tanto, el peso de las cubiertas de ciclo correspondientes en${\displaystyle G}$y${\displaystyle G'}$fósforo.

Tenga en cuenta que el tamaño de${\displaystyle G'}$es polinomial en${\displaystyle n}$y${\displaystyle \log W}$.

El objetivo aquí es reducir una matriz cuyas entradas son potencias de 2 a una matriz equivalente que contenga solo ceros y unos (es decir, un grafo dirigido donde cada arista tiene un peso de 1).

Dejar${\displaystyle G}$ser un${\displaystyle n}$-grafo dirigido de nodos donde todos los pesos en las aristas son potencias de dos. Construya un grafo,${\displaystyle G'}$, donde el peso de cada arista es 1 y${\displaystyle \operatorname {Perm} (G)=\operatorname {Perm} (G')}$. El tamaño de este nuevo gráfico,${\displaystyle (G')}$, es polinómico en${\displaystyle n}$y${\displaystyle p}$donde el peso máximo de cualquier arista en el grafo${\displaystyle G}$es${\displaystyle 2^{p}}$.

Esta reducción se realiza localmente en cada borde en${\displaystyle G}$que tenga un peso mayor que 1. Deje${\displaystyle e=(u,v)}$ser una ventaja en${\displaystyle G}$con un peso${\displaystyle w=2^{r}>1}$Se reemplaza por un subgrafo${\displaystyle J_{e}}$que está compuesto de${\displaystyle 2r}$nodos y${\displaystyle 6r}$bordes como se ve en la Figura 2. Cada borde en${\displaystyle J_{e}}$tiene un peso de 1. Por lo tanto, el gráfico resultante${\displaystyle G'}$Contiene únicamente aristas con un peso de 1.

Considere alguna cobertura de ciclo${\displaystyle R}$en${\displaystyle G}$.

• Si un borde original${\displaystyle e}$del gráfico${\displaystyle G}$no está en${\displaystyle R}$No se puede crear un camino a través del nuevo subgrafo.${\displaystyle J_{e}}$. La única forma de formar una cubierta de ciclo sobre${\displaystyle J_{e}}$En tal caso, cada nodo del subgrafo debe completar su propio bucle. Como cada arista tiene un peso de uno, el peso de la cobertura de ciclos resultante es igual al de la cobertura de ciclos original.
• Sin embargo, si la ventaja en${\displaystyle G}$es parte de la cubierta de ciclo entonces en cualquier cubierta de ciclo de${\displaystyle G'}$debe haber un camino desde${\displaystyle u}$a${\displaystyle v}$en el subgrafo. En cada paso hacia abajo del subgrafo hay dos opciones que se pueden tomar para formar dicho camino. Se debe tomar esta opción.${\displaystyle r}$veces, lo que resulta en${\displaystyle 2^{r}}$posibles rutas desde${\displaystyle u}$a${\displaystyle v}$Por lo tanto, hay${\displaystyle 2^{r}}$posibles coberturas de ciclo y dado que cada ruta tiene un peso de 1, la suma de los pesos de todas estas coberturas de ciclo es igual al peso de la cobertura de ciclo original.