Timeline for Finding the Length of the shortest Accepting path of a NDTM
Current License: CC BY-SA 3.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Sep 23, 2012 at 12:41 | vote | accept | Xavier Labouze | ||
| Feb 9, 2012 at 19:51 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
edited title
|
| Feb 9, 2012 at 17:56 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 174 characters in body
|
| Feb 9, 2012 at 17:30 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 290 characters in body
|
| Feb 8, 2012 at 22:31 | answer | added | vzn | timeline score: 0 | |
| Feb 8, 2012 at 22:05 | answer | added | Bruno | timeline score: 8 | |
| Feb 8, 2012 at 21:43 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
added 9 characters in body; edited title
|
| Feb 8, 2012 at 21:35 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 329 characters in body; edited title
|
| Feb 7, 2012 at 20:34 | comment | added | Xavier Labouze | @Bruno , Tks a lot - Do make your comment an answer. | |
| Feb 7, 2012 at 19:04 | comment | added | Bruno | I guess so. Let $L\in\mathsf{NP}$. It is decided by a NDTM $M$ in time $p(n)$. To turn an instance of $L$ into an instance of your problem, I do the following: I add a counter to $M$, and when on input $x$ it enters an accepting state, it loops until the counter reaches $p(|x|)$. Let $\tilde M$ be this NDTM. We have $x\in L\iff \tilde M$ halts on $x$ in exactly $p(|x|)$ computation steps. This gives a polytime reduction from any language $L\in\mathsf{NP}$ to your problem. | |
| Feb 7, 2012 at 11:11 | comment | added | Xavier Labouze | Yes, you are right. My post deals with $t$ polynomially bounded in the size of $x$ and the problem is "does $M$ halt on $x$ in exactly $t$ computation steps?" - Can it be considered NP-complete as well ? (since the "rank" of the computation step is directly accessible) | |
| Feb 7, 2012 at 8:54 | comment | added | Bruno | I am not sure what you mean by rank. If I am right, you mean the exact step when the TM halts on a particular input. Nevertheless, the following problem is $\mathsf{NP}$-complete: Given a NDTM $M$, an input $x$ and a time bound $t$, does $M$ halts on $x$ in at most $t$ computation steps. Does this help? | |
| Feb 7, 2012 at 8:26 | history | tweeted | twitter.com/#!/StackCSTheory/status/166800100507664384 | ||
| Feb 7, 2012 at 1:41 | history | edited | Xavier Labouze | CC BY-SA 3.0 |
deleted 2 characters in body
|
| Feb 7, 2012 at 1:24 | history | asked | Xavier Labouze | CC BY-SA 3.0 |