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!

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.)

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .