Timeline for Collapsing of exptime and alternation bounded turing machine
Current License: CC BY-SA 2.5
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 10, 2010 at 0:39 | comment | added | Ryan Williams | Here is one reference. See Theorem 3.2 in: oocities.com/[email protected]/pth.pdf. But this doesn't say that the problem is open for superpolynomial functions. I am not sure of a reference for that, but I do know that even if NEXP = EXP it is not known how to solve NEXP search problems in less than doubly-exponential time. This is essentially the same sort of problem you run into here. See Impagliazzo and Tardos 1989. | |
| Aug 9, 2010 at 23:12 | comment | added | Arthur MILCHIOR | As I wrote, I know for classes closed under composition(for linear TM you probably need many tape to make this true) I found the exact same problem then you when I tried to make the proof, (even if at first I was trying to make a descriptive complexity attemps, but that seems to be equivalent) My theory book is Arora Barak, which does not seems to discuss of bounded alternation after the poly-time classes, hence if you have got any references, both to state that this is open, and that under the condition that PTIME collapse it collapse, I'd like it please. Thanks for your help | |
| Aug 9, 2010 at 21:38 | history | answered | Ryan Williams | CC BY-SA 2.5 |