Timeline for Are runtime bounds in P decidable? (answer: no)
Current License: CC BY-SA 2.5
20 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 15, 2017 at 11:34 | comment | added | ghosts_in_the_code | @AaronSterling As long as the OP is fine with the edits, there is no problem in rephrasing a section of or even the entire answer. Writing new paras to describe something differently however should be preferably done in comments or a separate answer. (Unless of course, u want to make the answer a community wiki) And I think the automatic change to CW feature has been removed. | |
| Jul 16, 2013 at 8:38 | comment | added | David G | This answer inspired the following article: arxiv.org/abs/1307.3648 | |
| Mar 15, 2011 at 14:06 | comment | added | John Sidles | @Emanuele: As a heads-up, it appears that your theorem may be a special case of a result that is proved by Jules Hartmanis, on the final page of his monograph <i>Feasible computations and provable complexity properties</i> (1978) ... perhaps I'll post more about this, in a few days, once I have finished digesting Hartmanis' result. | |
| Feb 28, 2011 at 14:13 | comment | added | John Sidles | Aaron, your new "Nanoexplanations" weblog is outstanding and I greatly enjoyed your clarified proof. I've posted a comment there that begins: "Scott Aaronson is the author of a wonderful article titled 'Is P Versus NP Formally Independent?' I have often wished that Scott would write a similarly graceful and erudite followup 'Is P Versus NP Formally Undecidable?' One might say: 'Wait a second … wouldn't these be the same article?' To which the answer is: 'Formally yes … and yet, their guiding intuitions might be very different.'" Further comments on Aaron's new weblog would be very welcome. | |
| Feb 26, 2011 at 21:06 | comment | added | Aaron Sterling | I tried to rewrite this proof in my own words in this blog entry. | |
| Feb 18, 2011 at 23:16 | comment | added | John Sidles | Aaron is 100% right ... I had to parse Emanuele's post quite slowly (and enjoyably) in order to grasp its main point. | |
| Feb 18, 2011 at 23:05 | comment | added | Kaveh | @Raphael, I agree with @Aaron Sterling, editing heavily other user's answers has been a very common practice on cstheory. On the other hand you can post another answer trying to explain Emanuele's answer from your view point if you want. | |
| Feb 18, 2011 at 21:54 | comment | added | Raphael | @John: As long as no published reference is given, consider this guideline. | |
| Feb 18, 2011 at 21:52 | comment | added | Raphael | Ok, then lets do it like this: Emanuele, if you want me to potentially improve the understandibility of your otherwise great answer, please give the word! As I am low-rep, a mod will have to approve my edit, anyway. | |
| Feb 18, 2011 at 21:19 | comment | added | Aaron Sterling | @Raphael: That's a touchy area, which I don't think we've resolved. Some stackexchange sites encourage editing of others' answers. We don't have a policy against it, but, as a practical matter, I've almost never seen it done. One technical point: if an answer is edited too much, it becomes community wiki, and @Emanuele would not get any further rep points if his answer were upvoted after that. I do think additional explanation would help clarify: @John Sidles initially thought the promise was not being used, but the proof uses a stronger promise: $M'$ runs in $n^2$ or $n^3$, not just P. | |
| Feb 18, 2011 at 20:07 | comment | added | John Sidles | To second Antonio's comment, I would very much like to be able to cite a reference for Emanuele Viola's answer (also Luca Trevisan's answer to a related question, that was linked in the question as-hand). | |
| Feb 18, 2011 at 19:56 | comment | added | Antonio E. Porreca | Very clever proof, is it a variation of some well-known result or did you just devise it? | |
| Feb 18, 2011 at 19:41 | comment | added | Raphael | I think the reduction's central equivalence could have been stated/shown more clearly. Should I just edit and try to improve it? | |
| Feb 18, 2011 at 19:32 | comment | added | Raphael | John, $M$ is not necessarily in $P$. It is an arbitrarily chosen TM, otherwise you would not reduce the halting problem. | |
| Feb 18, 2011 at 17:47 | vote | accept | John Sidles | ||
| Feb 18, 2011 at 17:46 | comment | added | John Sidles | Upon one further reading (and careful parsing) your answer now has been "accepted"! Thank you for your trouble, and for a fine answer! | |
| Feb 18, 2011 at 17:26 | comment | added | John Sidles | Wow, TCS StackOverflow is great! Emanuele, one thing that baffles me is your answer's lack of reference to the promise that M is in P. Does the proof of the undecidability of the halting problem still go through, if the halting set is so restricted? This is not obvious to me (and I would need considerable time to work it through even imperfectly). | |
| Feb 18, 2011 at 17:18 | comment | added | Manu | $M$ and $x$ are fixed independent of $n$. | |
| Feb 18, 2011 at 17:12 | comment | added | Suresh Venkat | why does M have to halt on x (if it does) in O(1) steps ? | |
| Feb 18, 2011 at 17:09 | history | answered | Manu | CC BY-SA 2.5 |