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?



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.)

  • $\begingroup$ @ Emil: where do you use P = NP? PH \subset E, so E = E^PH . What am I missing? $\endgroup$ – LowerBounds Mar 8 '11 at 15:53
  • $\begingroup$ 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). $\endgroup$ – Emil Jeřábek supports Monica Mar 8 '11 at 15:58
  • $\begingroup$ @ Emil: My bad. I confused E and EXP. I meant to type: PH \subset EXP, so EXP = EXP^PH. Does EXP^EXP not equal EXP? $\endgroup$ – LowerBounds Mar 8 '11 at 16:52
  • $\begingroup$ 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$). $\endgroup$ – Emil Jeřábek supports Monica Mar 8 '11 at 17:07
  • $\begingroup$ @ 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? $\endgroup$ – LowerBounds Mar 8 '11 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.