Timeline for Collapsing of exptime and alternation bounded turing machine
Current License: CC BY-SA 2.5
9 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 9, 2010 at 23:17 | comment | added | Arthur MILCHIOR | @Dorais, I added "descriptive-complexity" because it is also a descriptive complexity problem, I translated the question at the end, but this is a real question about class of (high-order) formulae. So I do not really understand why you removed the tag. (In fact, I found this question studying those classes of formulae before I thought of it as a Turing Machine question) | |
| Aug 9, 2010 at 21:38 | answer | added | Ryan Williams | timeline score: 6 | |
| Aug 9, 2010 at 21:20 | history | rollback | François G. Dorais |
Rollback to Revision 3
|
|
| Aug 9, 2010 at 20:50 | history | edited | Arthur MILCHIOR |
added a tag
|
|
| Aug 9, 2010 at 19:19 | comment | added | Arthur MILCHIOR | @Salamon, what you state is true. By example, if C is the class of Elementary function, then alternation does not change the expressivity. I changed my question to add as a question: what are the condition over C for this theorem to be known. In particular, is it true for the class of Turing Machine that interest my current research (bounded tower of 2) And for finite model theory, it is a result by Turull-Toress and Heila that those classes are equal to those classes of TM. | |
| Aug 9, 2010 at 19:14 | history | edited | Arthur MILCHIOR | CC BY-SA 2.5 |
Trying to make the question more clear and correct latex typo
|
| Aug 9, 2010 at 19:09 | history | edited | Arthur MILCHIOR | CC BY-SA 2.5 |
added 26 characters in body
|
| Aug 9, 2010 at 18:59 | comment | added | András Salamon | If the class $C$ has a single function that grows fast enough, then as far as I can tell, it is possible to have zero alternations be as powerful as up to $k$, but for $k+1$ alternations to beat $k$. I suspect you weren't wanting to include such pathological examples: do you have a more precise formulation of your question? | |
| Aug 9, 2010 at 14:56 | history | asked | Arthur MILCHIOR | CC BY-SA 2.5 |