Complexidade da conversão de um circuito booleano em uma fórmula booleana

10

Dado um circuito booleano em variáveis ​​(que usa apenas portas NOT, AND e OR), qual é a maneira mais eficiente de extrair a fórmula booleana representada pelo circuito? Existe um algoritmo polytime para esse problema?nCn

Nikhil
fonte
que tipo de portas o circuito possui?
Lev Reyzin
11
Quais restrições à entrada ou saída de fãs? Se é apenas um fan-out, então é trivial: o circuito em si é essencialmente um AST para a fórmula.
Re: Mark Reitblatt
11
Fan-in limitado para ser geral. Mas, para ser mais preciso, digamos que AND e OR tenham fan-in 2. Em muitas referências na literatura, acho que um circuito e fórmulas são usados ​​de forma intercambiável, mas quero saber se é fácil converter um circuito em uma fórmula. problema.
Nikhil 11/02
6
Em geral, você esperaria que qualquer fórmula equivalente pudesse ter tamanho exponencial, mesmo para um pequeno circuito.
Kristoffer Arnsfelt Hansen
4
As fórmulas de tamanho polinomial são equivalentes aos circuitos . Os circuitos de polisização ( ) não são equivalentes a . As fórmulas e circuitos são usados ​​de maneira intercambiável geralmente quando a profundidade do circuito é limitada. NC1 N C 1P/polyNC1
Kaveh

Respostas:

8

Se eu entendi sua pergunta corretamente, eu diria que você poderia usar a redução padrão de CIRCUIT-SAT para SAT: represente cada porta como uma nova variável e, em seguida, represente todo o circuito no formato CNF, com cada cláusula no formato , em que é a nova variável, e a fórmula para o portão é fornecida por , usando as variáveis ​​para outros portões para representar as entradas. Isso pode ser feito por uma travessia simples (em tempo linear, o que é claramente ideal).v ϕ(vϕ)vϕ

Por exemplo, se você possuir três entradas, , e , com portas AND vinculando e , bem como e , e uma porta OR conectando suas saídas, poderá introduzir três variáveis ​​para representar as portas - , e , respectivamente - e reescreva a fórmula paraObserve que a variável de saída está incluída explicitamente.x 2 x 3 x 1 x 2 x 2 x 3 v 1 v 2 v 3 ( v 1( x 1x 2 ) ) ( v 2( x 2x 3 ) ) ( v 3( v 1v 2 ) ) v 3x1x2x3x1x2x2x3v1v2v3

(v1(x1x2))(v2(x2x3))(v3(v1v2))v3.

Introdução aos Algoritmos por Cormen et al. explica isso em detalhes, no capítulo NP-Completeness.

Magnus Lie Hetland
fonte
O CIRCUIT-SAT não usa portas 1 fan-out?
Re: Reitblatt
11
Claro - mas, tanto quanto posso ver, isso não afeta a redução / transformação. A idéia de representar cada saída como uma nova variável significa que você pode reutilizar cada saída como uma entrada várias vezes (correspondente a uma saída arbitrariamente grande). Em outras palavras, a solução dada nesta resposta deve funcionar para circuitos arbitrários.
Magnus Lie Hetland
3
Meu palpite seria que não é isso que está sendo pedido. Eu acho que o que se quer é fazer uma fórmula no mesmo conjunto de variáveis ​​que o circuito.
Kristoffer Arnsfelt Hansen
11
Hum. Sim, você provavelmente está certo. A introdução das novas variáveis ​​faz sentido no caso CIRCUIT-SAT para CNF-SAT, mas não em um cenário mais geral - eu concordo.
Magnus Lie Hetland
11
Cx1,x2,,xnϕ(x1,x2,,xn)