circuit le plus petit utilisant des portes XOR

15

Supposons que l'on nous donne un ensemble de n variables booléennes x_1, ..., x_n et un ensemble de m fonctions y_1 ... y_m où chaque y_i est le XOR d'un sous-ensemble (donné) de ces variables. Le but est de calculer le nombre minimum d'opérations XOR que vous devez effectuer pour calculer toutes ces fonctions y_1 ... y_m.

Notez que le résultat d'une opération XOR, disons x_1 XOR x_2 peut être utilisé dans le calcul de plusieurs y_j mais est compté comme un. Notez également qu'il pourrait être utile de calculer le XOR d'une collection beaucoup plus grande de x_i (plus grande que toute fonction y_i, par exemple le calcul du XOR de tous les x_i) afin de calculer les y_i plus efficacement,

De façon équivalente, supposons que nous ayons une matrice binaire A et un vecteur X et le but est de calculer le vecteur Y tel que AX = Y où toutes les opérations effectuées dans GF (2) en utilisant un nombre minimum d'opérations.

Même lorsque chaque ligne de A a exactement k (disons k = 3), c'est intéressant. Quelqu'un connaît-il la complexité (dureté de l'approximation) de cette question?

Mohammad Salavatiopur

Mohammad R. Salavatipour
la source

Réponses:

18

C'est NP-difficile. Voir: Joan Boyar, Philip Matthews, René Peralta. Techniques de minimisation logique avec applications à la cryptologie. http://link.springer.com/article/10.1007/s00145-012-9124-7

La réduction est de Vertex Cover et est très agréable.

Étant donné un graphique avec m = | E | , définissez une matrice m × ( n + 1 ) A comme: A [ i , j ] = 1 si j < n + 1 et ( i , j ) E , et A [ i , n({1,,n},E)m=|E|m×(n+1)UNEUNE[je,j]=1j<n+1(je,j)E . Enautres termes, étant donné n + 1 des variables x 1 , ... , x n + 1 , nous voulons calculer les m formes linéaires x i + x j + x n + 1 pour tous ( i , j ) E .UNE[je,n+1]=1n+1X1,,Xn+1mXje+Xj+Xn+1(je,j)E

Un peu de réflexion montre qu'il existe un circuit XOR pour avec des portes de ventilateur en deux calculant la transformation linéaire A avec seulement m + k portes, où k est la couverture de sommet optimale pour le graphique. (Calculez d'abord x i + x n + 1 pour tout i dans la couverture des sommets, en utilisant k opérations. Les formes linéaires sont ensuite toutes calculables en m opérations supplémentaires.) Il s'avère que c'est aussi un circuit de taille minimale!UNEUNEm+kkXje+Xn+1jekm

La preuve que la réduction est correcte n'est pas si agréable. J'aimerais voir une courte preuve que cette réduction est correcte.

Ryan Williams
la source
Merci Ryan. Document très pertinent en effet. Je pensais que le problème pouvait être aussi difficile que la couverture des sommets dans les hypergraphes, du moins dans le cas où vous ne générez pas de sommes XOR plus importantes (ce que j'appelle sans annulation dans cet article, je pense).
Mohammad R. Salavatipour
3
Pour le cas sans annulation, la dureté NP est notée à Garey-Johnson sous le nom quelque peu obscur "Ensemble Calcul" (Problème PO9, en A11.1). La réduction est en fait la même que celle décrite par Ryan, voir la section 3.2.2 dans GJ.
Janne H. Korhonen