# P = NP -> EXP has circuit size O(2^n/n)

How does this proof work / can someone provide a link to a paper? This is exercise 6.7 of Computational Complexity a Modern Approach. I know the following:

(1) P = NP -> EXP = NEXP (by padding) (2) exists f: {0,1}^n -> {0,1} that takes at least O(2^n/n) , by pigeon hole (3) any f:{0,1}^n -> {0,1} can be done in O(2^n/n), by Shannon's clever result from 49 (4) Looks like I'm supposed t use NEXP to "guess" a circuit of some sort.

I've also googled around, and there's references to some famous work by Razabov's work, I can't figure out which paper.

Question: What step am I missing in proving this classical, well known result?

Thanks!

-

If $P = NP$, then $E = EH := E^{PH}$. You can easily define the lexicographically first truth table of a Boolean function $f\colon\{0,1\}^n\to\{0,1\}$ with the maximum circuit complexity (which is $\sim2^n/n$ by Shannon and Lupanov) in $E^{\Sigma^p_2}$: find the maximum circuit complexity $s_\max$ by binary search using an oracle for “there exists a function with circuit complexity $\ge s$”, then find $f$ by binary search using an oracle for “there exists $g\le_{\mathrm{Lex}}f$ with circuit complexity $s_\max$”. (This argument is essentially due to Kannan who states it with $NE^{\Sigma^p_2}\cap coNE^{\Sigma^p_2}$. The strengthening with $E^{\Sigma^p_2}$ is basically folklore, an explicit proof is given in Lemma 2 of Miltersen, Vinodchadran & Watanabe.)
It's not true that $E^E=E$. Note that since exponential time is available, the oracle may be supplied with an exponentially long query! Thus, for example, $E^{NP}$ contains NE (and coNE). –  Emil Jeřábek Mar 8 '11 at 15:58
E or EXP does not make much of a difference here. $EXP^{EXP}$ does not equal EXP. In fact, $EXP^{EXP}=EEXP:=DTIME(2^{2^{n^{O(1)}}})$ by a padding argument (an EEXP problem can be computed by an EXP machine $M$ when the inputs are given with exponentially long padding; we can generate the padding by another EXP machine, and then pass it as an oracle query to $M$). –  Emil Jeřábek Mar 8 '11 at 17:07
@ Emil: Let $M_1, M_2 \in EXP$; $M_1$ using DTIME($2^{p1(n)}$), $M_2$ using DTIME($2^{p2(n)}$). Then, I can simulate $M_1^{M_2}$ in DTIME ($2^{ p1(n) + p2(n) }$). What am I doing wrong? –  LowerBounds Mar 8 '11 at 17:34