2
$\begingroup$

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.

In Yuval's answer here I've learned of two examples (Tardos function and bipartite perfect matching) where it has been proven that monotone circuits admit greater size than general Boolean circuits, but I cannot get the intuition, as I don't have any concrete small size example in hand.

Hence, my question is: could you please supply me with an example of a small (say, up to 10-20 gates) non monotone circuit such that any equivalent monotone circuit has greater size?

Edit

I guess that the smallest-size circuit computes the 3-Clique decision problem, as this is the smallest size where we can exploit fast matrix multiplication for the k-Clique problem (where non-monotone circuits may have smaller size than their equivalent monotone circuits, as I mentioned before).

Since the key part of exploiting fast matrix multiplication is (roughly): does $X^2$ contain any non-zero? Hence, I guess that a circuit that computes this decision problem is the minimal-size one. So, it is equivalent to $$\bigvee_{i,j,k\leq n}{(x_{ij}\wedge x_{jk})}\equiv\bigvee_{i,j\leq n}\left(x_{ij}\wedge{\left(\bigvee_{k\leq n} x_{jk}\right)} \right)$$.

If it is true, we just need to find some small $n$ (preferably, the smallest $n$), and some non-monotone function of size $\lneq n^2\cdot (n+1)=n^3+n^2$, which is the size of RHS, which is probably the minimal-size monotone circuit that computes this function.

Now, smallest size for Strassen is $n=4$, so it admits $n^2=4^2=16$ variables, but I guess that simpler manipulation than Strassen could do the desired on smaller $n$, and with simpler manner.

To sum up, I almost get it, but still do not have an explicit simple and small example in hand.

Improve this question
$\endgroup$
2
  • $\begingroup$ cs.stackexchange.com/q/90943/755 $\endgroup$
    – D.W. ♦
    Commented Apr 13, 2020 at 16:42
  • $\begingroup$ @D.W. I am aware of these two examples, but can't put them explicitly - could you please write down some concrete example? E.g, could you write down some non-monotone circuit that computes k-Clique and has $O(n^{0.8k})$ size for some small $n$? (as being mentioned in the link you cited) $\endgroup$
    – Dudi Frid
    Commented Apr 13, 2020 at 17:11

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.