Consequências práticas de

fundo

A complexidade do circuito é definida como o conjunto de famílias de circuitos (ou seja, sequências de circuitos, uma para cada tamanho de entrada) de profundidade limitada e tamanho polinomial construído usando a ventoinha ilimitada AND, OR e NOT.$AC^0$

A função de paridade com entrada de bits é igual ao XOR dos bits na entrada.$\oplus$$n$

Um dos primeiros circuitos inferiores comprovados em complexidade de circuitos é o seguinte:

[FSS81], [Ajt83]: .$\oplus \notin AC^0$

Questões:

Seja a classe de funções que podem ser calculadas usando circuitos eletrônicos de profundidade limitada e tamanho polinomial usando peças eletrônicas como transistores. (Inventei o nome , informe-me se souber um nome melhor para isso).$EC^0$$EC^0$

1. Podemos calcular na prática usando circuitos ?$\oplus$$EC^0$

2. E quanto ao fan-in ilimitado E / OU? Podemos computá-los em ?$EC^0$

3. Faz têm quaisquer consequências práticas? É importante na prática?$\oplus \notin AC^0$$AC^0$

4. Por que importante para os cientistas da computação (teóricos)?$\oplus \notin AC^0$

Nota:

Este post contém perguntas interessantes, mas o OP parece se recusar a tornar o post mais legível e corrigir os conceitos errados por algum motivo, por isso estou repondo perguntas. (Seria mais fácil editar a postagem original, mas atualmente não há um acordo se for correto editar fortemente a postagem de outro usuário.)

Relacionado:

• Paridade e$AC^0$

• Por que a paridade não é importante em ? $AC^0$(Blog da complexidade computacional)

Não sou engenheiro eletricista, mas busco patentes on-line sobre circuitos de comutação para portas de paridade e todas as propostas (encontrei patentes apenas até o final da década de 1970) discutem o problema de tamanho versus profundidade. Todas as três patentes analisadas propõem soluções de profundidade logarítmica, baseadas em portas fanin-2. Portanto, a resposta para sua primeira pergunta é possivelmente "não".

JJ Moyer: Circuito de comutação de verificação de paridade, patente dos Estados Unidos US3011073, 1961

AF Bulver et al .: realização do NAND Gate da função de paridade de entrada n, patente US3718904, 1973

PJ Baun, Jr .: Parity Circuits, Patente dos Estados Unidos US4251884, 1981

Johne, qual é o seu problema? Você está tentando discutir sobre coisas que ninguém jamais reivindicou. Ninguém disse que o limite inferior da paridade coloca algum limite fundamental para calcular o XOR com circuitos diferentes daqueles para os quais o teorema se aplica (ou seja, circuitos AC ^ 0). Não há suposições ocultas ou implicações veladas aqui. Em particular, todos sabemos, por exemplo, que é possível calcular o XOR com circuitos NAND de tamanho polinomial de profundidade logarítmica, mesmo com constante fan-in.

A citação de Shannon também é irrelevante. Não há indicação de que ele suspeite que os circuitos AND-OR de profundidade constante precisem ter tamanho exponencial para calcular a Paridade. É claro que ele deve ter adivinhado, já que é fácil conjeturar que isso deveria ser verdade depois de brincar com o problema por um tempo, mas e daí?

Você está perdendo completamente o ponto: provar limites mais baixos é extremamente difícil e precisamos começar em algum lugar, com os modelos mais simples. Esse foi essencialmente o primeiro limite do circuito, as técnicas levam a muitas idéias interessantes (incluindo outros campos, como a teoria da aprendizagem) e, embora o resultado seja plausível, a prova é perspicaz e nada trivial.

O fato de o resultado parecer intuitivo não o torna óbvio; se você pensa que é, forneça uma prova de que a paridade não está em AC ^ 0. Todo mundo sabe que P também não é igual a NP, mas ninguém está nem perto de ter uma prova.

Suas queixas em outros tópicos sobre portões NAND também não fazem sentido. Esse limite inferior se aplica igualmente a circuitos de profundidade constante construídos a partir de portas NAND, pois são basicamente os mesmos. Optar por declarar o resultado com AND, OR, NOT é apenas uma questão de conveniência. Portanto, essa pode ser uma aplicação do mundo real nos termos que você gosta: os circuitos de profundidade constante da paridade de computação das portas NAND requerem tamanho exponencial. Isso dá uma limitação prática, mesmo que isso não seja a coisa mais importante. Ele diz que pequenos circuitos XOR para um grande número de entradas n devem ter profundidade crescendo com n ou portas diferentes de NAND. Por que você não está satisfeito com isso?

Sua afirmação de que a profundidade do circuito não é um problema no mundo real também é muito enganadora, pois a profundidade está diretamente relacionada ao tempo e à frequência máxima com que o relógio pode operar.

A propósito, a comunidade de CS estava bem ciente da teoria do circuito booleano de EE e se baseou nela, ao contrário do que você afirma.

$1.62^2$$3.82^2$

• Estruturas de circuitos lógicos da tecnologia CMOS

$s = a \oplus b \oplus c_{in}$

• Célula de somador completo de alta velocidade e baixa potência 8T

Um bom lugar para encontrar portas XOR / XNOR compactas e de alta velocidade é nos somadores completos e nos circuitos de Hamming ECC (que normalmente estão no caminho crítico).

Além disso, a questão da profundidade do circuito normalmente não é uma preocupação na lógica síncrona VLSI. A única profundidade de qualquer consequência é o caminho crítico, que define o período máximo do relógio. A grande maioria da lógica combinatória propaga seus resultados em uma fração do tempo para o caminho crítico. Caminhos críticos tendem a ocorrer com alguma lógica combinatória que precisa passar por várias áreas espalhadas por um chip.

$n$$O(1)$

$AT^2 = \Omega(n^2)$

• Sobre a complexidade das implementações VLSI e representações gráficas de funções booleanas com aplicação na multiplicação de números inteiros

Isto é do Blog da complexidade da computação:

Isso levanta a questão: algumas pessoas no mundo real real realmente querem construir polisizadores de circuitos AND-OR-NOT de profundidade constante e ilimitada para o PARITY, e esse resultado diz a eles por que não podem?

$2^n/n$

$\lambda(3) = 8$

$X \oplus Y \oplus Z = X(YZ+Y'Z') + X'(YZ'+Y'Z)$

$\mu(3)$

$X_1 \oplus X_2 \oplus \ldots \oplus X_n$

$4(n-1)$