menor tamanho de circuito usando portas XOR

Suponha que recebamos um conjunto de n variáveis ​​booleanas x_1, ..., x_n e um conjunto de m funções y_1 ... y_m onde cada y_i é o XOR de um subconjunto (dado) dessas variáveis. O objetivo é calcular o número mínimo de operações XOR que você precisa executar para calcular todas essas funções y_1 ... y_m.

Observe que o resultado de uma operação XOR, digamos x_1 XOR x_2, pode ser usado no cálculo de vários y_j, mas é contado como um. Além disso, observe que pode ser útil computar o XOR de uma coleção muito maior de x_i (maior que qualquer função y_i, por exemplo, computar o XOR de todos os x_i) para computar o y_i com mais eficiência,

Equivalentemente, suponha que temos uma matriz binária A e um vetor X e o objetivo é calcular o vetor Y de modo que AX = Y, onde todas as operações são executadas em GF (2), usando o número mínimo de operações.

Mesmo quando cada linha de A tem exatamente k um (digamos, k = 3) é interessante. Alguém sabe sobre a complexidade (dureza de aproximação) desta pergunta?

Mohammad Salavatiopur

Isso é difícil para NP. Veja: Joan Boyar, Philip Matthews, René Peralta. Técnicas de Minimização Lógica com Aplicações em Criptologia. http://link.springer.com/article/10.1007/s00145-012-9124-7

A redução é da Vertex Cover e é muito agradável.

Dado um gráfico com m = | E | , defina uma matriz m × ( n + 1 ) A como: A [ i , j ] = 1 se j < n + 1 e ( i , j ) ∈ E , e A [ i , $(\{1,\ldots,n\},E)$$m=|E|$$m \times (n+1)$$A$$A[i,j] = 1$$j < n+1$$(i,j) \in E$ . Em outras palavras, dado n + 1 variáveis x 1 , ... , x n + 1 nós queremos calcular a m linear 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$

Um pouco de reflexão mostra que existe um circuito XOR para com portões de fan-in dois calculando a transformação linear A com apenas m + k portões, onde k é a cobertura de vértices ideal para o gráfico. (Primeiro calcule x i ' + x n + 1 para todos os i ' na cobertura do vértice, usando operações k . As formas lineares são todas computáveis ​​em m mais operações.) Acontece que este também é um circuito de tamanho mínimo!$A$$A$$m+k$$k$$x_{i'} + x_{n+1}$$i'$$k$$m$

A prova de que a redução está correta não é tão boa. Eu adoraria ver uma prova curta de que essa redução está correta.