Qual é a largura mínima da árvore de um circuito acima de para calcular o MAJ?
Aqui MAJ gera 1 se pelo menos metade de suas entradas for .1
Preocupo-me apenas com o tamanho do circuito (deve ser polinomial) e que uma entrada seja lida apenas uma vez, embora o ventilador de uma porta de entrada possa ser arbitrário (isso afeta crucialmente a largura da árvore do circuito - a ramificação programas obtidos do teorema de Barrington no MAJ , interpretados como circuitos de inclinação, não ajudam). E, claro, a largura da árvore é a coisa mais crucial. Eu não me importo com a profundidade ou qualquer outro parâmetro.N C 1
Alguns dos circuitos comuns para o MAJ incluem:
- Circuitos em árvore Wallace (por exemplo, Teorema 8.9 aqui ) que usam o truque 3 para 2 para colocar MAJ em ?
- Circuitos monótonos Valiant para MAJ (por exemplo, Teorema 4 aqui )
- rede de classificação em profundidade, como classificação em Lote
- Rede de classificação AKS
Algum deles tem largura de árvore limitada ou mesmo polilogarítmica?
Ou de fato,
Existem razões para acreditar que não há circuitos limitados de largura de árvore para o MAJ?
Observe que toda função calculada por um circuito delimitado de largura de árvore pode ser calculada por um circuito , mesmo quando não há estipulação de leitura única via JansenSarma . Assim, a implausibilidade de uma família de circuitos indica que esse limite pode ser mais apertado no caso de circuitos de leitura única.
Respostas:
Respondendo metade da pergunta de Samir.
Deixe ser um DAG e V 1 , V 2 ⊆ V ser dois subconjuntos de vértices de L . Denotamos por E ( V 1 , V 2 ) o conjunto de todas as arestas em G com um ponto final em V 1 e outro ponto final em V 2 . Se ω = ( v 1 , . . . , V n )G=(V,E) V1,V2⊆V G E(V1,V2) G V1 V2 ω=(v1,...,vn) G ω L O w ( L ) = min ω
Afirmamos que a MAJORIDADE de bits pode ser computada na largura online e, portanto, na largura da árvore . O circuito simula um algoritmo online que lê um bit de entrada por vez e adiciona a um contador com bits se e somente se . No início, o contador é inicializado emO ( log n ) O ( log n ) b b O ( log n ) b = 1 0 C = ( A D D 1 , A D D 2 , . . . , um D D N , C O M P ) A D D i A D D i + 1 A Dn O(logn) O(logn) b b O(logn) b=1 0 . No final, o circuito aceita se e somente se o valor do contador for maior que n / 2. É fácil ver que os portões de um ADD de circuito que adiciona um ao contador de registro podem ser ordenados topologicamente de forma a terem largura on-line constante, pois esses circuitos precisam apenas implementar uma operação de transporte. O circuito total é uma sequência de circuitos que a saída de é conectada à entrada de e a saída de é conectada ao entrada de COMP. Agora, se topologicamente o circuito total de tal maneira que todos os portões de apareçam antes dos portões de e todos os portões deC=(ADD1,ADD2,...,ADDn,COMP) ADDi ADDi+1 C A D D i A D D i + 1 A D D n O ( log n )ADDn C ADDi ADDi+1 ADDn aparece antes dos portões do COMP, então essa ordem topológica tem largura online . Essa construção é ilustrada na Figura 1 de um artigo meu para mostrar que a amplificação de probabilidade pode ser feita na largura on-line logarítmica.O(logn)
Obs: A profundidade do circuito C é .O(n)
fonte
Respondendo à outra metade da pergunta - aqui está um esboço de prova para um limite inferior de para a largura da árvore para alguma constante . O limite é independente do tamanho ou de qualquer outro aspecto do circuito. No resto do argumento é o circuito, é o treewidth de e é o número de portas de entrada.c C t C nc⋅logn c C t C n
O primeiro passo é usar o lema do separador balanceado para gráficos de largura de árvore limitada . As portas (incluindo as portas de entrada) do circuito podem ser divididas em três partes , e , de modo que e e contêm pelo menosportas de entrada, e não existem arcos (fios) entre e .R S | S | ≤ t + 1L R S |S|≤t+1 R n / 3 - | S | L RL R n/3−|S| L R
No restante da prova, a única propriedade do circuito que usaremos é esse particionamento - portanto, a prova fornece um limite mais baixo do tamanho de um separador balanceado como acima.S
Tendo em mãos, construímos um circuito partir de seguinte maneira: para cada porta em faça mais duas portas e e faça e alimentarem . Para todos os fios que levam a de faça-os entrar em . Para todos os fios que levam a de faça-os entrar em . Seja C ′ C g S g L g R g L g R g g L g L g R g R S ′ = { g , g L , g R : g ∈ S } .(L,S,R) C′ C g S gL gR gL gR g g L gL g R gR
Para cada uma das atribuições a faça um circuito que emita 1 se (a) a atribuição às portas de entrada tornar saída verdadeira e (b) a atribuição às portas de entrada definir todos os portões de como adivinhado. Chame esses circuitos , , para . Observe que o circuito naturalmente se divide em dois subcircuitos e modo que depende apenas das portas de entrada de , depende apenas das portas de entrada deS ′ C ′ S ′ C 1 C 2 C 3 … C x x ≤ 8 t C i C L i C R i C L i L ∪ S ′ C R i R ∪ S ′ C i = C L i ∧ C R Eu2|S′| S′ C′ S′ C1 C2 C3…Cx x≤8t Ci CLi CRi CLi L∪S′ CRi R∪S′ , e para qualquer atribuição para as portas de entrada temos que .Ci=CLi∧CRi
Como todas as atribuições para os portões de entrada são consistentes com algumas estimativas do que acontece em , temos que . Assim, reescrevemos o circuito como um OR (da ventoinha ) de AND (da ventoinha ) onde o número da porta AND está sendo alimentado com a saída de e respectivamente.C ′ = C 1 ∨ C 2 ∨ C 3 … ∨ C x C 8 t 2 i C L i C R iS′ C′=C1∨C2∨C3…∨Cx C 8t 2 i CLi CRi
Seja o conjunto dos portões AND mais altos. Primeiro provaremos que. Isso fornece um limite inferior simples para em . Vamos então provar um limite melhor.2 | Z | ≥ n / 3 - | S | log log n tZ 2|Z|≥n/3−|S| loglogn t
Suponha que, E assumir WLOG que contém menos portas de entrada que . Então e contêm pelo menosportões de entrada. Ao princípio o buraco pombo existem dois números diferentes e de tal modo que há duas designações diferentes para as portas de entrada de , que define portões a verdadeira, uma que conjuntos , de tal modo que os circuitos , produzem a mesma coisa. Mas existe uma atribuição para os portões de entrada em2|Z|<n/3−|S| L R L R n/3−|S| i j L i j CL1 CL2…CLx R de modo que MAJORITY produza FALSE se gates em estiverem configurados como true, e MAJORITY produz TRUE se gates em for configurada como true. Isso é uma contradição e, portanto, implicando que a largura da árvore é pelo menos .i L j L 2|Z|≥n/3−|S| loglogn
Agora mostramos um limite melhor:. Suponha WLOG que contém menos portas de entrada que . Então L e R contêm pelo menosportões de entrada. Considere o "tudo falso" atribuição para . Seja o menor número de portas de entrada de que deve ser configurado como true, de modo que MAJ produz TRUE, considerando que todo está definido como false.|Z|≥n/3−|S| L R n/3−|S| L r R L
Desde a criação para todos falsos e exatamente portões de entrada de para a saída verdadeiras marcas MAIORIA tem de haver algum tal que saídas TRUE, WLOG isso é . Todas as atribuições para com menos de portas de entrada verdadeiras devem definir como false. Como definir porta de entrada de como verdadeira e portas de entrada de como verdadeira produz a saída MAJORITY , definir porta de como verdadeira deve fazer pelo menos umar R 1 i C L i C L 1 R r C R 1 1 L r - 1 R 1 1 L C L i i ≠ 1 i = 2 R r - 2L r R 1 i CLi CL1 R r CR1 1 L r−1 R 1 1 L CLi é verdadeiro para . wlog, podemos assumir . Então, todas as atribuições para que configuram no máximo portas de entrada como true devem definir como false, e assim por diante - podemos repetir esse argumento vezes. Mas isso significa que, fornecendo um limite inferior de para .i≠1 i=2 R r−2 r | Z | ≥ r ≥ n / 3 - | S | c ⋅ log n tCR2 r |Z|≥r≥n/3−|S| c⋅logn t
[Estou ciente de que este esboço fica um pouco ondulado em alguns lugares, pergunte se algo não está claro ...]
fonte