Is there a simple example of a Boolean function $f:\{0,1\}^m \to \{0,1\}$ that we know can be computed by a polynomial-size circuit, but cannot be computed by any polynomial-size monotone circuit? Ideally, I'd be especially interested in a simple example where there is an exponential gap between the size of the smallest monotone circuit and the size of the smallest (not necessarily monotone) circuit.

Razborov's famous result shows that the $k$-clique function requires a monotone circuit of size $\Omega(n^k)$. In particular, we treat $x$ as the adjacency matrix of a graph and define $f(x)=1$ if the graph has a $k$-clique or 0 otherwise. However, this doesn't appear to provide a large gap between monotone circuit complexity and ordinary circuit complexity: the clique function can be computed by a monotone circuit of size $O(n^k)$, and the best known non-monotone circuit has size $O(n^{\omega k/3}) \approx O(n^{0.8k})$, where $\omega = 2.373...$ is the constant for matrix multiplication. This is not a very large gap: $O(n^k)$ vs $O(n^{0.8k})$. In particular, for choices of $k$ where the non-monotone complexity is polynomial, so is the monotone complexity.

Based on Razborov's result, Tardos has defined a function $\varphi$ that does have this exponential gap. However, $\varphi$ is fairly complex to even define: one must first introduce the Lovász number of a graph, then discuss how to approximate this number in polynomial time using linear programming, then show how to adjust the result to obtain the definition of the resulting function $\varphi$. In other words, the Tardos $\varphi$ function is not particularly simple to define.

So is there a suitable example that is simple/easy to define, and has a large gap between its monotone and non-monotone circuit complexity?

  • $\begingroup$ Are you aware of this? cs.cornell.edu/~eva/… $\endgroup$ – Yuval Filmus Apr 20 '18 at 19:28
  • $\begingroup$ @YuvalFilmus, thanks for reminding me of that! You're right, that's a suitable example -- except that I find it not particularly simple. So, I guess I'm really wondering if there is a simpler example, one where the function is easier to define. Question edited accordingly. $\endgroup$ – D.W. Apr 20 '18 at 20:54

Your Answer

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

Browse other questions tagged or ask your own question.