Timeline for Confusion about $EXP \subseteq P^{EXPCOM}$ claim from Arora and Barak
Current License: CC BY-SA 4.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 16, 2018 at 23:02 | comment | added | Yuval Filmus | My counterexample asks for a sequence of decidable languages $L_1,L_2,\ldots$ such that the language $\{(i,x) : x \in L_i\}$ is not decidable. | |
| Sep 16, 2018 at 18:02 | comment | added | panto | I didn't mean that $T$ takes $L$ as input no. Regarding your counter-example question, I guess the issue is that it gives you the ability to solve undecidable problems like the halting problem? (e.g., let $L$ be the unary language where $1^i \in L$ iff $M$ halts on input $x$ where $i$ encodes TM $M$ and input $x$. $L$ can be accepted by non-uniform TMs of course) | |
| Sep 5, 2018 at 6:38 | history | answered | Yuval Filmus | CC BY-SA 4.0 |