3
$\begingroup$

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!

$\endgroup$

1 Answer 1

1
$\begingroup$

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

$\endgroup$
7
  • $\begingroup$ @ Emil: where do you use P = NP? PH \subset E, so E = E^PH . What am I missing? $\endgroup$ Mar 8, 2011 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$ Mar 8, 2011 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$ Mar 8, 2011 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$ Mar 8, 2011 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$ Mar 8, 2011 at 17:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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