A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:
- fan-in=2 for the AND and OR nodes
- fan-n=1 for the NOT nodes
- fan-in=0 for the IN nodes
- fan-out=0 to exactly one node (the OUT node)
- Unbounded fan-out to the rest of the nodes (but the OUT node)
A monotone circuit is a Boolean circuit with 0 vertices labeled as "NOT".
The size of a circuit is the number of "gates" (vertices with labels "AND", "OR" or "NOT") it contains.
We know many lower bounds on the size of monotone circuits, that we do not know how to prove on a general Boolean circuit (such as this one on the Clique problem).
My question is: do we assume that lower bounds proven on monotone circuits apply also for equivalent general Boolean circuits (since they compute monotone function), and we just don't know how to prove it; or we assume\ know that these lower bounds do not apply to equivalent general Boolean circuits?
In the latter case, could you supply me with an example of a monotone function computed by both a monotone circuit and a general Boolean circuit, whilst the size of the monotone circuit is gretater than the general Boolean circuit? (I have been stuck on this for hours, seeking for such an example, so I believe that there is no such an example..)