Timeline for Non-existence of algorithm converting NP algorithm to P algorithm?
Current License: CC BY-SA 2.5
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 13, 2010 at 5:50 | history | edited | Ryan Williams | CC BY-SA 2.5 |
deleted 32 characters in body
|
| Jun 13, 2010 at 5:40 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added 1583 characters in body; added 1 characters in body
|
| Jun 12, 2010 at 23:55 | comment | added | Ryan Williams | See my comment above: this list of objects is just the set of all pairs {<N_i,k>} where N_1,N_2,... is an enumeration of all nondeterministic machines and k ranges over all positive integers. The pair <N_i,k> denotes the machine: "Given x, Simulate N_i(x) for some sequence of |x|^k+k steps. If N_i(x) hasn't already rejected, then reject." So we enforce that the simulation of N_i always runs in at most n^k+k steps. Now note that all NP languages are accepted by at least one machine in this list (in fact, infinitely many machines on the list). | |
| Jun 12, 2010 at 21:21 | comment | added | Tom Ellis | Ryan, could you please say more about that? | |
| Jun 12, 2010 at 19:04 | comment | added | Ryan Williams | Because there is another list of objects which also accept all NP languages, but this list can be easily recursively enumerated, whereas the other cannot. | |
| Jun 12, 2010 at 18:01 | comment | added | Tom Ellis | Ryan, could you please explain why "no complexity theorist ever deals with the input objects"? After all, those input objects are exactly those which accept an NP language (as opposed to a language which can be proved to be NP). | |
| Jun 12, 2010 at 14:15 | comment | added | Antonio E. Porreca | ...where by “given a polytime NDTM” I mean “given a NDTM that happens to run in polytime, but I’m not giving any proof”. | |
| Jun 12, 2010 at 14:08 | comment | added | Antonio E. Porreca | Ryan, now I understand what you meant; of course, you’re right in practice (I mean, if we have a polytime NDTM for some interesting NP-complete problem then, excluding pathological cases like Levin’s construction, we probably also know the polynomial) and the original question can indeed be interpreted this way. But I suspect the intended problem here is: given a polytime NDTM, map it to an equivalent polytime DTM; if the input machine is not polytime, you can output anything (since the domain is not decidable). It’d be interesting to know if this mapping cannot be computable (as it seems). | |
| Jun 12, 2010 at 12:44 | comment | added | Ryan Williams | The NP machines are typically constructed by taking an enumeration of nondeterministic Turing machines {N_i} and augmenting that with an enumeration (over all k) of "polynomial alarm clocks", so that the pair <N_i,k> denotes a machine that runs in at most n^k+k time on all inputs of length n, and after which it just rejects. That is, the set of NP machines is denoted by the set of all pairs {<N_i, k>}. This is quite standard and goes back to Hartmanis and Stearns' original paper on computational complexity. | |
| Jun 12, 2010 at 12:36 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added 76 characters in body; added 113 characters in body
|
| Jun 12, 2010 at 12:31 | comment | added | Ryan Williams | The alternative problem, of "given a nondeterministic machine which just so happens to run in polynomial time but has no built-in guarantee of the actual polynomial, output an equivalent deterministic machine which runs in polytime" is too strong, considering that no complexity theorist ever deals with the input objects. | |
| Jun 12, 2010 at 9:31 | comment | added | Antonio E. Porreca | Ryan, I’m sceptical too; deciding whether a TM runs in polytime is undecidable (is invoking Rice’s theorem enough to prove it?). I can’t immediately dismiss that knowing that the running time is polynomial might help finding the actual polynomial, but it doesn’t seem very convincing to me either. On the other hand, trying to use some form of the bounded halting problem might be a good idea. | |
| Jun 12, 2010 at 8:03 | comment | added | Adam | "We typically assume that the machine's running time is easily inferred from the code of the machine" -- that seems like a rather strong assumption. How might you go about computing whether the running time is finite or infinite? (obviously an easier problem that computing its precise running time!) | |
| Jun 12, 2010 at 7:35 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added 243 characters in body
|
| Jun 12, 2010 at 7:17 | history | edited | Ryan Williams | CC BY-SA 2.5 |
added 1 characters in body
|
| Jun 12, 2010 at 6:56 | history | answered | Ryan Williams | CC BY-SA 2.5 |