Timeline for Given a polynomial-time algorithm, can we compute an explicit polynomial time bound just from the program?
Current License: CC BY-SA 2.5
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 15, 2016 at 15:40 | comment | added | Peter Gerdes | Wait, don't we also need that the program k is never SLOWER (or at worst poly slower) than f(k)? For the contradiction we need that $\phi_k$ is polynomial time but not bounded by R(j). Hmm, I guess if one takes apart the recursion theory it turns out that the fixed point $k$ merely consists of a program which computes $f(k)$ in constant time and then simulates $f(k)$ and simulation will preserve poly time. The other direction allows the quick fix of just outputting sufficiently many 1s to ensure $\phi_k$ is slow enough. | |
| Jun 15, 2010 at 2:12 | comment | added | Carl Mummert | Yes, that statement is right. I did some searching and that sort of thing is already present in the computational complexity literature, and I'm sure it must be well known to people who study complexity. It took me a moment to see the issue because I tend to think of the recursion theorem in terms of its proof rather than as a pure existence statement. Very informally: because the proof is uniform, the only way to imitate an arbitrary function is going to be to actually run it, so the amount of slowdown is the main thing that needs to be checked. | |
| Jun 15, 2010 at 1:11 | comment | added | Joel David Hamkins | +1. Thanks, Carl! It's very nice. Your fix exactly addresses the point I was trying to make. It seems that your argument proves a version of the Recursion Theorem where one gets control over how long the function takes to conpute. Can you make a precise statement about this? I guess it shows something like: if $f$ is any total computable function, then there is a program $k$ for which $\phi_k=\phi_{f(k)}$, and program $k$ is never faster than $f(k)$ on any input and at worst polynomial time slower? | |
| Jun 14, 2010 at 3:18 | history | edited | Carl Mummert | CC BY-SA 2.5 |
expand on recursion theorem
|
| Jun 14, 2010 at 2:21 | comment | added | Carl Mummert | I'm sorry, it took me a minute to see your point. I do need the proof of the recursion theorem, from that point of view. I'll expand the answer to clarify. | |
| Jun 14, 2010 at 1:52 | comment | added | Joel David Hamkins | Carl, I'm a bit confused by your argument. Since the function $C_k$ is identically 0, mightn't the Recursion Theorem simply give me a program k that computes this function very quickly? In this case, I don't see the contradiction. That is, it seems that from $\phi_k=C_k$, we cannot deduce that time bounds are the same, since these programs may compute the same function in different ways. Or do you have in mind a deeper appeal to the proof of the Recursion Theorem, rather than just its statement, in which you get access to how the fixed point program works as well as the function it computes? | |
| Jun 13, 2010 at 20:17 | history | answered | Carl Mummert | CC BY-SA 2.5 |