Timeline for Non-existence of algorithm converting NP algorithm to P algorithm?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Apr 13, 2017 at 12:58 | history | edited | CommunityBot |
replaced http://mathoverflow.net/ with https://mathoverflow.net/
|
|
| Jun 16, 2010 at 22:40 | comment | added | Tom Ellis | I'm really not sure what I'm looking for as I have no experience of complexity theory, and this question just came into my head one day. It's served a good purpose, which is to give me plenty to think about in this field. Thanks for all your help everyone and when I slowly work through your writings I'll let you know if I have further questions! | |
| Jun 16, 2010 at 20:25 | comment | added | Timothy Chow | I somehow missed the fact that Ryan updated his answer. I see that he exploits the fact that in your statement of the problem, you don't require your output to be clocked either. I guess if you consider that to be "useful output" then what I said isn't quite right. If that is really what you are looking for then perhaps I should delete my answer as not addressing your question. | |
| Jun 16, 2010 at 20:07 | comment | added | Ryan Williams | @Tim: In fact, it's only uncomputable if you insist on a non-standard definition of nondeterministic time. @Tom: I would be happy to answer your questions about my answer... | |
| Jun 16, 2010 at 18:39 | comment | added | Carl Mummert | The difference here seems to be the distinction between "definition 1" and "definition 2". In the other question, we were looking at Turing machines that we know accept in polynomial time; this is more similar to definition 2 than to definition 1. Except we were looking at total polynomial-time functions, while definition 2 is about NP-semi-decidable sets. | |
| Jun 16, 2010 at 18:06 | comment | added | Tom Ellis | Ryan's answer above states that there is a computable mapping from unclocked NP machines to P machines. I haven't understood his answer yet, but that's unmistakably what he's claiming. | |
| Jun 16, 2010 at 17:40 | history | answered | Timothy Chow | CC BY-SA 2.5 |