Timeline for Are there any natural theories T for which P=NP implies T proves P=NP?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jan 2, 2017 at 8:15 | comment | added | Will Sawin | No, this doesn't work, for exactly the reason you state. It's not possible to enumerate polynomial-time Turing machines in the way you are suggesting - telling if a fixed Turing machine halts in polynomial time - as this would enable you to solve the halting problem by considering Turing machines that ignore their input and hence either halt in constant time or run forever. | |
| Dec 3, 2016 at 2:36 | history | edited | none | CC BY-SA 3.0 |
added 231 characters in body
|
| Dec 3, 2016 at 2:28 | history | edited | none | CC BY-SA 3.0 |
added 482 characters in body; deleted 2 characters in body
|
| Dec 3, 2016 at 2:24 | review | First posts | |||
| Dec 3, 2016 at 4:19 | |||||
| Dec 3, 2016 at 2:20 | history | answered | none | CC BY-SA 3.0 |