Considere uma linguagem não vazia de cadeias binárias de comprimento . Posso descrever com um circuito booleano com entradas e uma saída tal que seja verdadeira se : isso é bem conhecido.n L C n C ( w ) w ∈ L
No entanto, quero representar com um Booleano circuito de com saídas e um certo número de entradas, por exemplo , de tal modo que o conjunto dos valores de saída para cada um dos possíveis entradas é exactamente .C ′ n m C ′ 2 m L
Dado , como posso encontrar um circuito de tamanho mínimo e qual é a complexidade? Existe alguma relação entre limites conhecidos sobre o tamanho dos circuitos do primeiro tipo ( ) e circuitos deste segundo tipo ( ), ou a complexidade de encontrá-los?C ′ C C ′
(Observe que existe algum tipo de dualidade no seguinte sentido: dado , eu posso facilmente decidir se uma palavra de entrada está em avaliando o circuito, mas é geralmente difícil para NP encontrar alguma palavra em encontrando Dado , é igualmente NP difícil decidir se alguma palavra de entrada está em porque eu tenho que ver se uma atribuição produz como saída, mas é fácil encontrar alguma palavra em avaliando o circuito em qualquer entrada arbitrária.)w L L C ′ w L w L
Respostas:
Vou apontar uma conexão simples com circuitos não determinísticos e comentar brevemente sobre a dureza criptográfica.
Para , defina a complexidade da imagem, denominada , como o número mínimo de portas em qualquer circuito booleano (fanin-two, AND / OR / NOT) , cuja imagem é . A pergunta pergunta sobre a complexidade da computação , dada uma representação da tabela verdade de (uma sequência de comprimento ). i m c ( S ) C : { 0 , 1 } m → { 0 , 1 } n S i m c ( S ) S 2 nS⊆{0,1}n imc(S) C:{0,1}m→{0,1}n S imc(S) S 2n
Defina também a complexidade do circuito não determinístico de , que iremos designar , como o menor circuito não determinístico aceitar exatamente . Ou seja, exigimos de que se . Essa é uma noção padrão, usada para definir a classe não uniforme : é a classe de todos os conjuntos , com , de modo que .n c c ( S ) C ( x , y ) : { 0 , 1 } n + m ′ → { 0 , 1 } S C x ∈ S ∃ y : C ( x , y ) = 1 N P / p o l y S = { S n } n > 0S ncc(S) C(x,y):{0,1}n+m′→{0,1} S C x∈S ∃y:C(x,y)=1 NP/poly S={Sn}n>0 Sn⊆{0,1}n ncc(Sn)≤poly(n)
O que eu queria ressaltar é que . Ambas as direções dessa desigualdade são simples de verificar.imc(S)=ncc(S)±O(n)
Seja denotar a complexidade determinística do circuito. Usando Razborov-Rudich, o artigo que Dai Le menciona mostra (grosso modo aqui) que sob certas suposições criptográficas, é computacionalmente difícil distinguir tabelas verdadeiras de com pequenas, de tabelas verdadeiras de verdadeiramente aleatório ( com quase-máximo). aleatórios também têm quase-máximo, e é claro que temos . Portanto, seu problema é difícil sob as mesmas suposições.S d c c ( S ) S d c c ( S ) S n c c ( S ) n c c ( f ) ≤ d c c ( f )dcc(S) S dcc(S) S dcc(S) S ncc(S) ncc(f)≤dcc(f)
O que é mais difícil de calcular, dada uma tabela de verdade para , ou ? Existe uma redução de qualquer maneira? Eu não sei.d c c ( S ) n c c ( S )S dcc(S) ncc(S)
fonte
Você deve dar uma olhada neste artigo de Kabanets e Cai. Vou citar o resumo do artigo:
Embora o circuito você mencionou calcule uma função , podemos pensar nele como uma sequência de circuitos , onde calcula o pouco de saída . Como cada calcula uma função booleana , minimizar os circuitos parece difícil de acordo com o resultado acima.C′ F:{0,1}m→L C′1,C′2,…,C′n C′i ith F C′i {0,1}m→{0,1} C′i
fonte