<p>I don't think the paper in the other answer contains an answer to your question. Indeed I am not really sure a proof has been published, because the result follows from other well known results. </p>

<p>The proof of the statement you want is as follows: </p>

<ol>
<li><p>$\Sigma_3 E$ contains a function of maximum possible circuit complexity on every input length, by simply defining a function which proves itself (using alternation) to be different from all functions with non-maximum circuit complexity. This is standard and the proof idea can be found in sources such as Arora and Barak's textbook.</p></li>
<li><p>If $P = NP$ then $\Sigma_3 E = E$, by padding and the collapse of the polynomial time hierarchy to $P $.</p></li>
<li><p>Therefore if $P = NP$ then there is a language in $E$ with maximum circuit complexity. This is the contrapositive of what you want to prove.</p></li>
</ol>

CC BY-SA 3.0
2015-10-16T07:27:27.337Z
Nice, I guessed that you would be the first one to answer it.
Mohammad Al-Turkistany
CC BY-SA 3.0
2015-10-17T03:33:56.237Z
There is also an answer in the  paper of Kabanets and Cai. In Theorem 10 they prove that if $MCSP$ is in $P$, then $E^{NP}$ contains a family of Boolean functions of maximum circuit complexity. If $P=NP$, then $MCSP\in P$ and $E^{NP}=E$, so then, by the Theorem, $E$ indeed contains a language with maximum complexity.
Andras Farago
CC BY-SA 3.0
2015-10-17T05:37:00.007Z
good point, Andras! One of the quantifiers in the  $\Sigma_3 E $ part can be seen as solving  MCSP.
Ryan Williams
CC BY-SA 3.0
2015-10-16T07:20:01.847Z
2015-10-17T03:46:59.657Z
2015-10-17T03:46:59.657Z
Ryan Williams
<p>googling around found me this paper which was published with the refrence below.</p>
<blockquote>
<p>Circuit minimization problem</p>
<p><strong>Valentine Kabanets and Jin-Yi Cai</strong></p>
<p><em>We study the complexity of the circuit minimization problem: given the truth table of a Boolean function f and a parameter s, decide whether f can be realized by a Boolean circuit of size at most s. We argue why this problem is unlikely to be in P (or even in P/poly) by giving a number of surprising consequences of such an assumption. We also argue that proving this problem to be NP-complete (if it is indeed true) would imply proving strong circuit lower bounds for the class E, which appears beyond the currently known techniques.</em></p>
</blockquote>
<p>This appeared to be published below.</p>
<ol>
<li><p>extended abstract in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC'00), pages 73-79, 2000.
technical report, in Electronic Colloquium on Computational Complexity TR99-045, 1999.
<a href="http://www.cs.sfu.ca/%7Ekabanets/Research/circuit.html" rel="noreferrer">http://www.cs.sfu.ca/~kabanets/Research/circuit.html</a></p>
</li>
<li><p>extended abstract in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC'00), pages 73-79, 2000.
<a href="http://eccc.hpi-web.de/report/1999/045/" rel="noreferrer">http://eccc.hpi-web.de/report/1999/045/</a></p>
</li>
</ol>

CC BY-SA 3.0
2015-10-26T00:34:56.247Z
Note that this answer doesn't answer the above question but it does provide the reference which this question originated in.
Joshua Herman
CC BY-SA 3.0
2015-10-16T02:30:54.380Z
2015-10-16T02:30:54.380Z
2020-06-17T09:38:08.363Z
Joshua Herman
<p>In the official Clay problem description for P versus NP it's stated that $P \neq NP$ would follow from showing that "every language in $E$ [the class of languages recognizable in exponential time with a deterministic Turing machine] can be computed by a Boolean circuit family $&lt;B_n&gt;$ such that for at least one $n$, $B_n$ has fewer gates than the maximum needed to
compute any Boolean function $f: \{0,1\}^n \longrightarrow \{0,1\}$." However, the only reference is that this "is an intriguing observation by V. Kabanets." Could someone please point me to a published version of this implication with the proof?</p>

<cc.complexity-theory><circuit-complexity>
Proof that circuit upper bounds for $E$ imply $P \neq NP$
David
# Proof that circuit upper bounds for $E$ imply $P \neq NP$

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

In the official Clay problem description for P versus NP it's stated that $P \neq NP$ would follow from showing that "every language in $E$ [the class of languages recognizable in exponential time with a deterministic Turing machine] can be computed by a Boolean circuit family $$ such that for at least one $n$, $B\_n$ has fewer gates than the maximum needed to
compute any Boolean function $f: \{0,1\}^n \longrightarrow \{0,1\}$." However, the only reference is that this "is an intriguing observation by V. Kabanets." Could someone please point me to a published version of this implication with the proof?

**Tags:** cc.complexity-theory, circuit-complexity


---

## 2 answers

### Answer by username_1 on 2015-10-16. Score: 25

I don't think the paper in the other answer contains an answer to your question. Indeed I am not really sure a proof has been published, because the result follows from other well known results.

The proof of the statement you want is as follows:

1. $\Sigma\_3 E$ contains a function of maximum possible circuit complexity on every input length, by simply defining a function which proves itself (using alternation) to be different from all functions with non-maximum circuit complexity. This is standard and the proof idea can be found in sources such as Arora and Barak's textbook.
2. If $P = NP$ then $\Sigma\_3 E = E$, by padding and the collapse of the polynomial time hierarchy to $P $.
3. Therefore if $P = NP$ then there is a language in $E$ with maximum circuit complexity. This is the contrapositive of what you want to prove.

> **Comments:**
> **username_2**: Nice, I guessed that you would be the first one to answer it.  
> **username_3**: There is also an answer in the  paper of Kabanets and Cai. In Theorem 10 they prove that if $MCSP$ is in $P$, then $E^{NP}$ contains a family of Boolean functions of maximum circuit complexity. If $P=NP$, then $MCSP\in P$ and $E^{NP}=E$, so then, by the Theorem, $E$ indeed contains a language with maximum complexity.  
> **username_1**: good point, Andras! One of the quantifiers in the  $\Sigma_3 E $ part can be seen as solving  MCSP.  

---

### Answer by username_4 on 2015-10-16. Score: 6

googling around found me this paper which was published with the refrence below.

> Circuit minimization problem
>
> **Valentine Kabanets and Jin-Yi Cai**
>
> *We study the complexity of the circuit minimization problem: given the truth table of a Boolean function f and a parameter s, decide whether f can be realized by a Boolean circuit of size at most s. We argue why this problem is unlikely to be in P (or even in P/poly) by giving a number of surprising consequences of such an assumption. We also argue that proving this problem to be NP-complete (if it is indeed true) would imply proving strong circuit lower bounds for the class E, which appears beyond the currently known techniques.*

This appeared to be published below.

1. extended abstract in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC'00), pages 73-79, 2000.
   technical report, in Electronic Colloquium on Computational Complexity TR99-045, 1999.
   [http://www.cs.sfu.ca/~kabanets/Research/circuit.html](http://www.cs.sfu.ca/%7Ekabanets/Research/circuit.html)
2. extended abstract in Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing (STOC'00), pages 73-79, 2000.
   <http://eccc.hpi-web.de/report/1999/045/>

> **Comments:**
> **username_4**: Note that this answer doesn't answer the above question but it does provide the reference which this question originated in.  

---

