Menor circuito booleano para gerar um idioma

10

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 LLnLCnC(w)wL

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 LLCn mC2mL

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 LCCC

(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 LCwLLCwLwL

a3nm
fonte
2
Este artigo não responder à sua pergunta, mas estuda o tipo de circuitos que você está procurando eccc.hpi-web.de/report/2012/079
Marcos Villagra
pelos seus comentários abaixo, parece que você deseja considerar uma família de circuitos onde não é finito. adivinhar sua função também deve ser surjective e não pode ser bijective em geral ...L
vzn
11
Como é dado ? Pelo circuito ? CLC
usul

Respostas:

11

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}nimc(S)C:{0,1}m{0,1}nSimc(S)S2n

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 > 0Sncc(S)C(x,y):{0,1}n+m{0,1}SCxSy:C(x,y)=1NP/polyS={Sn}n>0Sn{0,1}nncc(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)Sdcc(S)Sdcc(S)Sncc(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 )Sdcc(S)ncc(S)

Andy Drucker
fonte
5

Você deve dar uma olhada neste artigo de Kabanets e Cai. Vou citar o resumo do artigo:

Estudamos a complexidade do problema de minimização de circuitos: dada a tabela verdade de uma função booleana e um parâmetro , decidimos se pode ser realizado por um circuito booleano de tamanho no máximo . Argumentamos por que é improvável que esse problema esteja em (ou mesmo em ), fornecendo uma série de conseqüências surpreendentes de tal suposição. Também argumentamos que provar que esse problema é -completo (se é realmente verdade) implicaria provar limites fortes de circuito mais baixos para a classe , que aparece além das técnicas atualmente conhecidas.s f s P P / p o l yfsfsPP/polyNPE

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.CF:{0,1}mLC1,C2,,CnCiithFCi{0,1}m{0,1}Ci

Dai Le
fonte
Obrigado! No entanto, eu não desejo para realizar um fixo função com o meu circuito : Estou OK com percebendo qualquer função , desde que a sua imagem é . Portanto, não estou tentando resolver o problema de realizar uma determinada função , então não acho que esse resultado de dureza ainda se aplique. fCfLf
a3nm
Acabei de atualizar minha resposta para resolver seu comentário.
Dai Le
11
Eu ainda discordo. Cada calcula uma função booleana como você diz, mas ainda existem várias opções possíveis para cada , mesmo assumindo que as outras sejam corrigidas. Por exemplo, se for , se for corrigido, ainda tenho várias opções para . Estou interessado na dureza de encontrar um circuito mínimo para conseguir algumas escolhas consistentes de tais funções booleanas, por isso não vejo uma redução do problema deles no meu. C i L { 000 , 001 , 010 , 011 } C 2 C 3CiCiL{000,001,010,011}C2C3
a3nm
11
Eu adicionei mais explicações.
Dai Le
11
@SashoNikolov Você está certo que não precisa calcular o eu mencionei. Ele pode calcular as cujo alcance é . Portanto, não sabemos como calcular que calcula de . Vou remover essa construção enganosa. F F L C f C CFFLCfC
Dai Le