É assumido que os limites inferiores no tamanho dos circuitos monótono se aplicam aos circuitos booleanos gerais também?

Question

a "geral" circuito booleano (combinatoiral) é rotulado (com os rótulos: e, ou, não, in, out), dirigido, gráfico acíclico, que satisfaz:

.
1. fã-in= 2 para o e ou ou nós
2. fan-n= 1 para os nós não
3. fã-in= 0 para os em nós
4. fan-out= 0 a exatamente um nó (o nó fora)
5. fan-out ilimitado para o resto dos nós (mas o nó fora)

a monotone circuito é um circuito booleano com 0 vértices rotulados como "não".

O tamanho de um circuito é o número de "portões" (vértices com etiquetas "e", "ou" ou "ou" não ") contém.

Sabemos muitos limites inferiores no tamanho dos circuitos monótono, que não sabemos como provar sobre um circuito general booleano (como este um no problema do clique).

Minha pergunta é: assumimos que os limites inferiores comprovados em circuitos monótono aplicam também para equivalente circuitos booleanos gerais (desde que eles compõem a função monótona), e nós apenas não sabemos como provar isso ; ou assumimos que sabemos que esses limites inferiores não se aplicam a circuitos booleanos gerais equivalentes?

No último caso, você poderia me fornecer um exemplo de uma função monótona calculada por um circuito monótono e um circuito general booleano, enquanto o tamanho do circuito monótono é Gretater do que o circuito booleano geral? (Eu fui preso por horas, buscando tal exemplo, então acredito que não há tal exemplo ..)

Answer 1

Éva Tardos deu a um função que pode ser calculado por um circuito geral de tamanho polinomial, mas requerum circuito monótono de tamanho exponencial.O circuito calcula uma boa aproximação suficiente para a função Lovász Theta do gráfico de entrada.

Razborov deu uma $ n ^ {\ Ômega (\ Log n)} $ Circuitos de monótono inferior limitados Computando a função de correspondência perfeita bipartita, para o qual os circuitos gerais do tamanho polinomialexistem.