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.
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. "
cc.complexity-theory
lower-bounds
circuit-complexity
Alexander S. Kulikov
fonte
fonte
Respostas:
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… Xn∨ x¯1 1… X¯n 2 n - c
fonte
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 é3 ⌊ n / 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 de3 ⌊ n / 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 .
fonte