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 $<B_n>$ 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?
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
3
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:
$\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.
If $P = NP$ then $\Sigma_3 E = E$, by padding and the collapse of the polynomial time hierarchy to $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.
answered Oct 16, 2015 at 7:20
-
$\begingroup$ Nice, I guessed that you would be the first one to answer it. $\endgroup$ Commented Oct 16, 2015 at 7:27
-
4$\begingroup$ 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. $\endgroup$ Commented Oct 17, 2015 at 3:33
-
1$\begingroup$ good point, Andras! One of the quantifiers in the $\Sigma_3 E $ part can be seen as solving MCSP. $\endgroup$ Commented Oct 17, 2015 at 5:37
$\begingroup$
$\endgroup$
1
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.
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
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/
-
$\begingroup$ Note that this answer doesn't answer the above question but it does provide the reference which this question originated in. $\endgroup$ Commented Oct 26, 2015 at 0:34