Timeline for Non-existence of algorithm converting NP algorithm to P algorithm?
Current License: CC BY-SA 2.5
22 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 16, 2010 at 17:40 | answer | added | Timothy Chow | timeline score: 3 | |
| Jun 13, 2010 at 19:37 | comment | added | Ryan Williams | Under the usual definition of nondeterministic time, the map is computable even if you do not know the running time bound. Please read my answer and if you do not agree with it, please state why. | |
| Jun 13, 2010 at 19:03 | comment | added | Joel David Hamkins | I agree with your expectation, but since I wasn't able to see how to prove it, I posted this question: mathoverflow.net/questions/28056/… | |
| Jun 12, 2010 at 18:16 | comment | added | Tom Ellis | Joel, certainly it appears difficult and I would imagine it's not a computable problem, since I suspect (but don't know -- I'm no complexity theorist) that it's non-computable to deduce a polynomial bound for runtime for a machine whose runtime you know is polynomially bounded. | |
| Jun 12, 2010 at 18:04 | comment | added | Joel David Hamkins | Tom, a polynomial time counter is just a part of the program that counts steps, in a fixed regular manner, up to a fixed particular polynomial, forcing a halt when the counter reaches this value. It is not difficult to see that every set in P is decidable by a program having such a counter, and it is easy to recognize from a program with such a counter that the program will always halt in that polynomial number of steps. What seems difficult is to computably transform a polytime algorithm without such a counter to one with such a counter, and this appears to be at the heart of your question. | |
| Jun 12, 2010 at 17:57 | comment | added | Tom Ellis | Ryan I do not know what a polynomial time counter is, but I have updated my question. Is that phrasing more appropriate for those familiar with the field? | |
| Jun 12, 2010 at 17:56 | history | edited | Tom Ellis | CC BY-SA 2.5 |
added 147 characters in body
|
| Jun 12, 2010 at 15:53 | comment | added | Joel David Hamkins | Tom, you misunderstood my remark. I like your interpretation, and I think the question is quite clear that your input does not come with a polynomial-time counter certificate. (But it appears that complexity theory people usually assume otherwise...) | |
| Jun 12, 2010 at 12:55 | comment | added | Ryan Williams | @Tom: You should rewrite your question if you do not assume your input is "verifiably NP". If you open up any text in complexity and see "...given a nondeterministic polytime machine...", that is referring to an object from the set of all nondeterministic machines augmented with a polynomial time counter. | |
| Jun 12, 2010 at 12:15 | comment | added | Tom Ellis | @Joel, Adam's point was rather vague. In any case, I'm not asking for the input to be verifiably NP, just assuming that we've been given one, map it to an equivalent P one. | |
| Jun 12, 2010 at 11:41 | comment | added | Joel David Hamkins | Tom, Adam's point is that we cannot computably recognize such programs---it is a nondecidable set of programs. Nevertheless, there is an easily recognized subclass of these problems which cover all the P sets, namely, those that we can easily observe have a polynomial counter built in that makes them halt in polynomial time, but the question is asked for a transformation of all polytime programs, not just those of a special form. This is the uniformity issue that arose in the comments to Nate's answer below. | |
| Jun 12, 2010 at 10:11 | comment | added | Tom Ellis | @Adam, Like Antonio I don't understand. By "P-time Turing machine", I mean a Turing machine such that there exists a polynomial $p$ and which always halts on all input and which takes no longer than $p(n)$ time to halt, where $n$ is the length of the input string. These are exactly the Turing machines that accept a P language, aren't they? | |
| Jun 12, 2010 at 9:35 | comment | added | Antonio E. Porreca | Adam, why do you say that there isn’t such a thing as an x-time TM? | |
| Jun 12, 2010 at 7:59 | comment | added | Adam | "A polynomial-time non-deterministic Turing machine" -- there really isn't such a thing as an "X-time Turing machine". I think you want to rephrase your question replacing this with "instance of Z" where Z is some problem known to be NP-complete, or "arbitrary program accompanied by a formal proof that it halts in polynomial time". In the latter case you'll need to get specific about what form the proof takes. | |
| Jun 12, 2010 at 6:56 | answer | added | Ryan Williams | timeline score: 10 | |
| Jun 12, 2010 at 1:21 | comment | added | Antonio E. Porreca | I removed my (wrong) previous comment. This question appears to be much more interesting than it seemed at first glance. | |
| Jun 11, 2010 at 21:54 | history | edited | Tom Ellis | CC BY-SA 2.5 |
added 70 characters in body
|
| Jun 11, 2010 at 21:01 | vote | accept | Tom Ellis | ||
| Jun 11, 2010 at 21:05 | |||||
| Jun 11, 2010 at 20:59 | answer | added | Nate Eldredge | timeline score: 4 | |
| Jun 11, 2010 at 20:46 | comment | added | Tom Ellis | I'm not asking to check whether the input determines L, but whether, given that the input does accept some language produce a deterministic machine that accepts the same language. | |
| Jun 11, 2010 at 20:37 | comment | added | Akhil Mathew | There is no algorithm even for checking whether the non-deterministic Turing machine decides a language L (by the unsolvability of the halting problem). | |
| Jun 11, 2010 at 20:34 | history | asked | Tom Ellis | CC BY-SA 2.5 |