I am interested about the minimal size (number of gates) of a family of circuits (with negation) over a complete Boolean basis (with fanin 2) that computes some explicit Boolean function. (In other words, I want results that apply for a specific function, not diagonalization, counting, or non-constructive arguments). I call $n$ the number of inputs.

Section 1.5.2 of Boolean Function Complexity by Stasys Jukna (2011) says that the best such lower bound currently known is in $5n - \text{o}(n)$, from Iwama and Morizumi in 2002. This is very surprising, because, as Shannon proved in 1949 by a counting argument, most Boolean functions require exponential-size circuits.

Is the $5n - \text{o}(n)$ result still the best known? Is there any reason why proving a super-linear lower bound on the circuit size of an explicit function seems out of reach? In particular, do we know that solving this would close long-standing open problems in complexity theory as well?

  • 1
    $\begingroup$ There is no superliner size lower bound known for explicit circuits. I think it would make a more interesting question to ask about obstacles to proving such results than just asking if there is one known (this is a well known open problem). There are some good suggestions on MO about how to ask a good question about open problems. $\endgroup$
    – Kaveh
    Commented Oct 8, 2015 at 21:47
  • 1
    $\begingroup$ @Kaveh: The last sentence of my question is a bit asking about that. But if it's well-known that this problem is open, I'm totally OK with closing the question (or just getting that as an answer). $\endgroup$
    – a3nm
    Commented Oct 9, 2015 at 8:51
  • $\begingroup$ AFAIK it is, see e.g. this. Also related: 1, 2, 3 $\endgroup$
    – Kaveh
    Commented Oct 9, 2015 at 12:42
  • $\begingroup$ @Kaveh "There is no superliner size lower bound known for explicit circuits".. what is definition of an explicit circuit? is this related to P/NP at all and if so how? $\endgroup$
    – Turbo
    Commented Aug 6, 2016 at 22:24


Your Answer

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