tamaño de circuito más pequeño con puertas XOR

Supongamos que se nos da un conjunto de n variables booleanas x_1, ..., x_n y un conjunto de funciones m y_1 ... y_m donde cada y_i es el XOR de un subconjunto (dado) de estas variables. El objetivo es calcular el número mínimo de operaciones XOR que necesita realizar para calcular todas estas funciones y_1 ... y_m.

Tenga en cuenta que el resultado de una operación XOR, digamos x_1 XOR x_2 podría usarse en el cálculo de múltiples y_j, pero se cuenta como uno. Además, tenga en cuenta que podría ser útil calcular XOR de una colección mucho mayor de x_i (más grande que cualquier función y_i, por ejemplo, calcular XOR de todos los x_i) para calcular y_i de manera más eficiente,

De manera equivalente, supongamos que tenemos una matriz binaria A y un vector X y el objetivo es calcular el vector Y de manera que AX = Y donde todas las operaciones se realizan en GF (2) utilizando un número mínimo de operaciones.

Incluso cuando cada fila de A tiene exactamente k uno (digamos k = 3) es interesante. ¿Alguien sabe acerca de la complejidad (dureza de la aproximación) para esta pregunta?

Mohammad Salavatiopur

Esto es NP-duro. Ver: Joan Boyar, Philip Matthews, René Peralta. Técnicas de minimización lógica con aplicaciones a la criptología. http://link.springer.com/article/10.1007/s00145-012-9124-7

La reducción es de Vertex Cover y es muy agradable.

Dado un gráfico con m = | E | , defina una matriz A × m ( n + 1 ) como: A [ i , j ] = 1 si j < n + 1 y ( i , j ) ∈ E , y A [ i , $(\{1,\ldots,n\},E)$$m=|E|$$m \times (n+1)$$A$$A[i,j] = 1$$j < n+1$$(i,j) \in E$ . En otras palabras, dado n + 1 variables de x 1 , ... , x n + 1 queremos calcular la m lineales formas x i + x j + x n + 1 para todos ( i , j ) ∈ E .$A[i,n+1] = 1$$n+1$$x_1,\ldots,x_{n+1}$$m$$x_i+x_j+x_{n+1}$$(i,j) \in E$

Un poco de reflexión muestra que hay un circuito XOR para con compuertas de dos ventiladores que calculan la transformación lineal A con solo m + k compuertas, donde k es la cubierta de vértice óptima para el gráfico. (Primero calcule x i ′ + x n + 1 para todo i ′ en la cubierta del vértice, usando k operaciones. Las formas lineales son entonces computables en m más operaciones). ¡Resulta que este también es un circuito de tamaño mínimo!$A$$A$$m+k$$k$$x_{i'} + x_{n+1}$$i'$$k$$m$

La prueba de que la reducción es correcta no es tan buena. Me encantaría ver una breve prueba de que esta reducción es correcta.