Timeline for Which was the first novel set in universes where P=NP?
Current License: CC BY-SA 3.0
5 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Dec 16, 2015 at 18:15 | comment | added | zwol | IIRC, it has been proven that P=PSPACE (which is stronger than P=NP) for a Turing machine equipped with the ability to send data backward in time, even if it's subject to Novikov self-consistency. It is still possible that P=PSPACE for ordinary Turing machines, but this is considered even less plausible than P=NP by 'mainstream' complexity theorists. | |
| Jun 8, 2012 at 10:51 | comment | added | M.K. | Yes, if his test was successful, it would have meant that there is a 'stronger' computation device than the Turing machine and therefore he disproved Church's thesis. So if you leave NP defined using Turing machines, it wouldn't prove 'NP = P'. | |
| Jun 6, 2012 at 8:51 | comment | added | Tadeusz A. Kadłubowski | That doesn't make sense. A problem belongs into P, if a certain Turing machine solving this problem exists (definition of NP is similar). It doesn't matter whether there are other conceivable means of solving this problem. By hacking time loops Harry got beyond P=NP question. | |
| Jan 14, 2012 at 18:48 | history | edited | DVK-on-Ahch-To | CC BY-SA 3.0 |
added 2 characters in body
|
| May 25, 2011 at 22:51 | history | answered | M.K. | CC BY-SA 3.0 |