<p>I am interested about the <em>minimal size</em> (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.</p>

<p>Section 1.5.2 of <em>Boolean Function Complexity</em> by Stasys Jukna (2011) says that the best such lower bound currently known is in $5n - \text{o}(n)$, from <a href="http://www.wisdom.weizmann.ac.il/~ranraz/publications/P5nlb.pdf" rel="noreferrer">Iwama and Morizumi</a> in 2002. This is very surprising, because, as Shannon proved in 1949 by a counting argument, most Boolean functions require exponential-size circuits.</p>

<p>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?</p>

CC BY-SA 3.0
2015-10-08T21:47:27.203Z
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
CC BY-SA 3.0
2015-10-09T08:51:11.833Z
@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).
Antoine Amarilli 'a3nm'
CC BY-SA 3.0
2015-10-09T12:42:45.180Z
AFAIK it is, see e.g. [this](http://cstheory.stackexchange.com/a/1004/). Also related: [1](http://cstheory.stackexchange.com/q/27470/), [2](http://cstheory.stackexchange.com/a/21401/), [3](http://cstheory.stackexchange.com/a/8005/)
Kaveh
CC BY-SA 3.0
2016-08-06T22:24:41.410Z
@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
<reference-request><circuit-complexity><boolean-functions><open-problem>
Why can't we have superlinear bounds on Boolean circuit size for an explicit function?
Antoine Amarilli 'a3nm'
# Why can't we have superlinear bounds on Boolean circuit size for an explicit function?

(Asked by: username_0 on 2015-10-08)

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](http://www.wisdom.weizmann.ac.il/~ranraz/publications/P5nlb.pdf) 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?

**Tags:** reference-request, circuit-complexity, boolean-functions, open-problem
> **Comments:**
> **username_1**: 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.  
> **username_0**: @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).  
> **username_1**: AFAIK it is, see e.g. [this](http://cstheory.stackexchange.com/a/1004/). Also related: [1](http://cstheory.stackexchange.com/q/27470/), [2](http://cstheory.stackexchange.com/a/21401/), [3](http://cstheory.stackexchange.com/a/8005/)  
> **username_2**: @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?  

---

## 0 answers

