Timeline for Do the undecidable attributes of P pose an obstruction to deciding P versus NP? (answer: maybe)
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 20, 2011 at 20:39 | comment | added | John Sidles | ... and just to mention, those language L that are recognized solely by Turing machines whose runtime exponents were undecidable, are interesting languages from a complexity-theoretic (and cryptographic) point-of-view ... they seemingly exist in a Godel-esque "gray region" between algorithmically compressible (but by definition not verifiably so) and incompressible (and yet by definition not in that class either). | |
| Jun 20, 2011 at 20:15 | comment | added | John Sidles | Yes ... that trick is the essence of Emanuele Viola's and Juris Harmanis' proofs of P's runtime undecidability (for example). On the other hand, it is trivially the case that the Turing machines that are constructed by this trick all recognize languages L that are also recognized by Turing machines in P whose runtimes are decidable. This is why Q1 is phrased (carefully!) as a question about languages rather than about Turing machines ... precisely in order to exclude the Hartmanis/Viola construction ... without obstructing (per your comment) the existing proofs that P \ne EXP. | |
| Jun 20, 2011 at 19:54 | history | answered | Lance Fortnow | CC BY-SA 3.0 |