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
8 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 15, 2010 at 1:13 | vote | accept | Joel David Hamkins | ||
| Jun 14, 2010 at 2:16 | history | edited | Timothy Chow | CC BY-SA 2.5 |
Corrected proof according to Francois Dorais's fix
|
| Jun 14, 2010 at 2:03 | comment | added | Joel David Hamkins | Timothy, thanks very much for this answer! Could I ask you kindly to edit the answer to incorporate François' fix? | |
| Jun 13, 2010 at 20:35 | comment | added | Carl Mummert | +1. For the converse, if we know that a program runs in polynomial time then we can use an oracle for the halting problem to find a polynomial upper bound. Just check all the polynomials, one after another, until you find one that is an upper bound. The property that a given total program does not run in a fixed time bound is Sigma^0_1 and so it can be answered by a query to the halting problem. This shows that the lower bound you give is sharp. (P.S. I doubt that the Turing reduction I describe here could be improved to a stronger reduction.) | |
| Jun 13, 2010 at 20:22 | comment | added | Timothy Chow | @Francois: Yes, that does it...thanks! | |
| Jun 13, 2010 at 19:55 | comment | added | François G. Dorais | Here is a fix: Let $M_i$ keep running for $n^s$ steps where $s$ is the number of steps it takes the machine $N_i$ to converge. Then you can solve the halting problem by reading the exponent of any polynomial upper bound. | |
| Jun 13, 2010 at 19:43 | history | edited | Timothy Chow | CC BY-SA 2.5 |
added 152 characters in body
|
| Jun 13, 2010 at 19:36 | history | answered | Timothy Chow | CC BY-SA 2.5 |