A "general" Boolean (combinatoiral) circuit is a labeled (with the labels: AND, OR, NOT, IN, OUT), directed, acyclic graph, that satisfies:

  1. fan-in=2 for the AND and OR nodes
  2. fan-n=1 for the NOT nodes
  3. fan-in=0 for the IN nodes
  4. fan-out=0 to exactly one node (the OUT node)
  5. 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..)


Éva Tardos gave a function which can be computed by a polynomial size general circuit but requires an exponential size monotone circuit. The circuit computes a good enough approximation to the Lovász theta function of the input graph.

Razborov gave an $n^{\Omega(\log n)}$ lower bound monotone circuits computing the bipartite perfect matching function, for which polynomial size general circuits exist.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.