Número de portas binárias necessárias para calcular AND e OR de n bits de entrada simultaneamente

16

Qual é o número mínimo de portas binárias necessárias para calcular AND e OR de bits de entrada simultaneamente? O limite superior trivial é 2 n - 2 . Eu acredito que isso é ótimo, mas como provar isso? A técnica de eliminação de gate padrão não funciona aqui, pois, ao atribuir uma constante a qualquer uma das variáveis ​​de entrada, trivializamos uma das saídas.n2n-2

O problema também é dado como um exercício 5.12 no livro "A complexidade de funções booleanas" por Ingo Wegener em uma forma ligeiramente diferente: "Vamos By. o método de eliminação pode-se provar apenas um limite inferior do tamanho n + Ω ( 1 ) . Tente provar limites inferiores maiores. "fn(x)=x1 1...xnx¯1 1...x¯nn+Ω(1 1)

Alexander S. Kulikov
fonte
11
@ Ryan: A questão não é sobre AND de OR, mas sobre AND e OR. Eu não sei a resposta para a pergunta de Sasha, no entanto.
Tsuyoshi Ito
11
@TsuyoshiIto Obrigado, de alguma forma eu consegui analisá-lo incorretamente. Definitivamente, é um problema não trivial - alguém poderia imaginar usar outros tipos de portas para obter uma vantagem sobre . 2n2
Ryan Williams
2
@ Sasha, você já tentou aplicar os solucionadores SAT em pequenos exemplos (como ), como em alguns de seus artigos anteriores? n=4
Ryan Williams
2
@ Ryan Sim, com certeza. O que sabemos é que , C 4 = 5 , C 57 . Isto é para a função do livro (é 1 se todos os n bits de entrada forem iguais). Isso cresce como 2 n - 3 . E um circuito de tamanho 2 n - 3 é fácil de construir: primeiro compute x ix i + 1 para todo i = 1 , ... , n -C3=3C4=5C571 1n2n-32n-3xEuxEu+1 1 ( ( n -Eu=1 1,...,n-1 1 portões) e depois calcule a conjunção deles ( ( n - 2 ) portões). (n-1 1)(n-2)
Alexander S. Kulikov
11
@Tsuyoshi: Eu acho que o portas funcionar de Sasha é a segunda função da questão ( f n ( x ) = x 1 ... x nˉ x 1 ... ˉ x n ) que pode ser construída com n - 1 XNOU portões (aplicado a x i , x i + 1 ) e n - 2 portas AND aplicado às XNORs. 2n-3fn(x)=x1 1...xnx¯1 1...x¯nn-1 1xEu,xEu+1 1n-2
Marzio De Biasi

Respostas:

14

Este artigo de Blum & Seysen pode ser útil:

N. Blum, M. Seysen. Caracterização de todas as redes ótimas para uma computação simultânea de AND e NOR . Acta Inf. 21: 171-181 (1984)

Eu pensei que para 2 n - c limite inferior pode ser obtida usando métodos de Blum & Seysen, mas parece que este não é o caso.x1 1...xnx¯1 1...x¯n 2n-c

Vladimir Lysikov
fonte
11
Existe uma versão pública em pdf do artigo de Blum e Seysen disponível?
Marzio De Biasi
@ Vladimir, obrigado pela referência! Tentarei verificar se os métodos deles são aplicáveis ​​nesse caso quando encontrar o artigo.
Alexander S. Kulikov
3
@ Vladimir, obrigado novamente! Na verdade, este artigo contém exatamente a resposta para minha pergunta e ainda mais: ele diz que, para calcular AND e OR simultaneamente, é necessário e qualquer circuito desse tamanho calcula AND e OR independentemente (isso é interessante!). Também não é difícil mostrar que C ( f n ) C ( A N D , O R ) - c 2 n - c . 2n-2C(fn)C(UMAND,OR)-c2n-c
Alexander S. Kulikov
@ Sasha, sim, eu perdi essa construção simples. Para esclarecer as coisas, no papel e e NOR funções são consideradas, portanto, para AND e OR temos limite inferior alterando um portão e para x 1 ... x nˉ x 1 ... ˉ x n --- 2 n - 52n-2x1 1...xnx¯1 1...x¯n2n-5
Vladimir Lysikov
11
Apenas um lembrete para @SashaK. se você gostar da resposta, "aceite" clicando na marca de seleção abaixo da contagem de votos.
Suresh Venkat
3

Sua pergunta está relacionada à pergunta conhecida sobre como calcular o mínimo e o máximo de uma lista simultaneamente, usando o número mínimo de comparações. Nesse caso, a resposta é 3n/2 .

O algoritmo inteligente que comprova o limite superior se traduz em um circuito AND / OR com o mesmo limite que você obtém, pois uma das comparações calcula um mínimo e um máximo.

No entanto, o limite inferior (fornecido por um argumento adversário) parece traduzir, pelo menos no caso de circuitos monotônicos (uma vez que um circuito AND / OR se traduz em um algoritmo max / min). Isso implicaria um limite inferior de 3n/2 . Talvez um limite inferior apertado possa ser obtido analisando o argumento do adversário.

O limite superior aparece em "Introdução aos algoritmos", onde você também pode encontrar o argumento fácil que mostra que os circuitos comparadores máx / min são válidos se eles trabalharem para entradas booleanas (use um limite apropriado). O limite inferior pode ser encontrado, por exemplo, aqui .

Yuval Filmus
fonte
2
Observe na pergunta de Sasha, todas as funções booleanas de 2 bits podem ser usadas para construir o circuito.
Ryan Williams
Sim, não está claro como o limite inferior pode ser convertido para o caso de todas as funções binárias.
Alexander S. Kulikov