Si presume che i limiti inferiori sulle dimensioni dei circuiti monotoni si applicano anche ai circuiti generali booleani?

Question

A "General" Il circuito booleano (combinato) è un etichettato (con le etichette: e, o, non, in, out), diretto, grafico acyclico, che soddisfa:

.
1. Fan-in= 2 per il nuovo e o o nodi
2. fan-n= 1 per i nodes
3. Fan-in= 0 per i nodi in
4. fan-out= 0 a esattamente un nodo (il nodo out)
5. Fan-out illimitato al resto dei nodi (ma il nodo fuori)

A Monotone Circuito è un circuito booleano con 0 vertici etichettati come "non".

La dimensione di un circuito è il numero di "cancelli" (vertici con etichette "e", "o" o "non") contiene.

Conosciamo molti limiti inferiori sulle dimensioni dei circuiti monotoni, che non sappiamo come dimostrare su un circuito generale booleano (come Questo

del problema della clique).

La mia domanda è: Assumiamo che i limiti inferiori dimostrati sui circuiti monotoni si applicano anche per equivalenti circuiti booleani generali (poiché calcolano funzione monotono), e semplicemente non sappiamo come dimostrarlo ; Oppure assumiamo \ sapere che questi limiti inferiori non si applicano ai circuiti equivalenti del booleano generale?

In quest'ultimo caso, potresti fornirmi con un esempio di una funzione monotono calcolata sia da un circuito monotono che da un circuito booleano generale, mentre la dimensione del circuito monotono è Gretater rispetto al circuito generale booleano? (Sono stato bloccato su questo per ore, cercando un esempio del genere, quindi credo che non ci sia un esempio di un esempio ..)

Answer 1

éva Tardos ha dato un Funzione che può essere calcolata da un circuito generale di dimensione polinomiale ma richiedeun circuito monotono dimensione esponenziale.Il circuito calcola un'approssimazione sufficientemente buona alla funzione Lovász Theta del grafico di ingresso.

Razborov ha dato una $ n ^ {\ omega (\ log n)} $ circuiti monotoni rilegati inferiori che calcolano la funzione di corrispondenza perfetta bipartite, per la quale i circuiti generali delle dimensioni polinomialiesistono.