Timeline for Diagonalization and classes of computable functions
Current License: CC BY-SA 3.0
4 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| May 5, 2012 at 7:51 | comment | added | Bjørn Kjos-Hanssen | Hadn't thought of that but that makes sense too... because the "right" $\phi_{e_0}$ is visited polynomially (quadratically) often even if you don't know which $e=e_0$... | |
| May 5, 2012 at 7:31 | comment | added | Noah Schweber | Oh, of course. If I recall correctly, this method also works to provide an explicit polynomial-time algorithm for SAT under the assumption P=NP. Thanks! | |
| May 5, 2012 at 7:31 | vote | accept | Noah Schweber | ||
| May 5, 2012 at 7:14 | history | answered | Bjørn Kjos-Hanssen | CC BY-SA 3.0 |