menor tamanho de circuito usando portas XOR

15

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

Mohammad R. Salavatipour
fonte

Respostas:

18

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 , n({1,,n},E)m=|E|m×(n+1)AA[i,j]=1j<n+1(i,j)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]=1n+1x1,,xn+1mxi+xj+xn+1(i,j)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!AAm+kkxi+xn+1ikm

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.

Ryan Williams
fonte
Obrigado Ryan. Papel muito relevante, de fato. Pensei se o problema poderia ser tão difícil quanto a cobertura de vértices nos hipergrafos, pelo menos para o caso de você não gerar somas XOR maiores (o que eu acho que é livre de cancelamento neste artigo).
Mohammad R. Salavatipour 13/08/2015
3
Para o caso sem cancelamento, a dureza NP é observada em Garey-Johnson sob o nome um tanto obscuro "Ensemble Computation" (Problema PO9, em A11.1). A redução é realmente a mesma descrita por Ryan, consulte a Seção 3.2.2 no GJ.
Janne H. Korhonen