Timeline for P = NP -> EXP has circuit size O(2^n/n)
Current License: CC BY-SA 2.5
11 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 6, 2011 at 7:17 | comment | added | Kaveh | Hi Email. Arora and Barak explicitly request in the preface of their book that people do not post online answers to the exercises in the book. Based on the questions of this user, it seems to me that this user is posting a number of homework question on MO. I am not sure, but IIRC people don't answer homework questions on Mathoverflow. | |
| Mar 8, 2011 at 17:42 | comment | added | Emil Jeřábek | You are ignoring the fact which I am now repeating for the third time, namely that oracle queries can have exponential length. During your simulation, $M_1$ makes some queries to $M_2$. Since the running time of $M_1$ is $2^{p_1(n)}$, the oracle queries can also have length up to $m=2^{p_1(n)}$. When $M_2$ is simulated on inputs of size $m$, it can take time $2^{p_2(m)}=2^{p_2\left(2^{p_1(n)}\right)}$, which is doubly exponential in $n$. | |
| Mar 8, 2011 at 17:34 | comment | added | LowerBounds | @ 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? | |
| Mar 8, 2011 at 17:10 | history | edited | Emil Jeřábek | CC BY-SA 2.5 |
One more try. The fucking thing works in the preview, but not live.
|
| Mar 8, 2011 at 17:07 | comment | added | Emil Jeřábek | 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$). | |
| Mar 8, 2011 at 17:00 | history | edited | Emil Jeřábek | CC BY-SA 2.5 |
some references
|
| Mar 8, 2011 at 16:52 | comment | added | LowerBounds | @ 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? | |
| Mar 8, 2011 at 15:58 | comment | added | Emil Jeřábek | 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). | |
| Mar 8, 2011 at 15:53 | comment | added | LowerBounds | @ Emil: where do you use P = NP? PH \subset E, so E = E^PH . What am I missing? | |
| Mar 8, 2011 at 15:20 | vote | accept | LowerBounds | ||
| Mar 8, 2011 at 15:52 | |||||
| Mar 8, 2011 at 14:25 | history | answered | Emil Jeřábek | CC BY-SA 2.5 |