# Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

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?

• 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. – Kaveh Oct 8 '15 at 21:47
• @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). – a3nm Oct 9 '15 at 8:51
• AFAIK it is, see e.g. this. Also related: 1, 2, 3 – Kaveh Oct 9 '15 at 12:42
• @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? – Turbo Aug 6 '16 at 22:24