Timeline for Which was the first novel set in universes where P=NP?
Current License: CC BY-SA 3.0
35 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 2, 2018 at 3:53 | answer | added | jersey | timeline score: 0 | |
| Feb 16, 2016 at 11:57 | answer | added | Broklynite | timeline score: 3 | |
| Feb 15, 2016 at 19:58 | history | reopened |
alexwlchan Reinstate Monica - Goodbye SE user14111 Jason Baker Null♦ |
||
| Feb 15, 2016 at 19:56 | review | Reopen votes | |||
| Feb 15, 2016 at 19:58 | |||||
| Feb 15, 2016 at 13:28 | history | edited | SQB |
edited tags
|
|
| Feb 15, 2016 at 12:56 | history | edited | SQB |
edited tags
|
|
| Sep 10, 2013 at 13:03 | review | Reopen votes | |||
| Sep 10, 2013 at 16:27 | |||||
| Sep 9, 2013 at 13:02 | review | Reopen votes | |||
| Sep 9, 2013 at 13:20 | |||||
| Sep 26, 2012 at 9:08 | history | edited | AncientSwordRage♦ | CC BY-SA 3.0 |
Added a picture and an attempt at explanation
|
| Sep 26, 2012 at 8:38 | history | edited | AncientSwordRage♦ | CC BY-SA 3.0 |
Tried to edit to re-open the question.
|
| Jul 26, 2012 at 19:50 | history | closed | user56 | not constructive | |
| Feb 29, 2012 at 20:03 | comment | added | Plutor | @DrG: Greg Egan could probably write a novel where P and NP are the protagonists. That guy makes Kim Stanley Robinson look like George Lucas. | |
| Jan 31, 2012 at 0:31 | history | edited | Kevin | CC BY-SA 3.0 |
added 7 characters in body; edited title
|
| Jan 14, 2012 at 18:46 | history | edited | DVK-on-Ahch-To | CC BY-SA 3.0 |
deleted 54 characters in body
|
| Jan 7, 2012 at 0:12 | comment | added | Kyle Jones | @Wikis: In a P=NP universe finding a correct solution to a large and well defined hierarchy of problems would be only as complex as recognizing that a proposed solution to such a problem is correct. For example, in our universe recognizing that a work of art is great seems to be much easier than creating a great work. In a universe where P=NP the amount of effort required would be the same or only modestly greater when looked at in terms of the size of the problem to be solved. Easy cracking of almost all forms of encryption is another sign of a P=NP universe. | |
| Jan 5, 2012 at 13:50 | comment | added | Reinstate Monica - Goodbye SE | Can you explain, in really simple terms, what P=NP means and how we'd know if a book we're reading would be in that universe? | |
| Jan 5, 2012 at 0:12 | answer | added | Kyle Jones | timeline score: 81 | |
| Sep 28, 2011 at 15:38 | comment | added | Brian Knoblauch | Maybe all of them... Since it's an unsolved problem at this moment. :-) | |
| Sep 27, 2011 at 1:38 | answer | added | Michael Kohne | timeline score: -2 | |
| Sep 25, 2011 at 23:42 | answer | added | deworde | timeline score: 26 | |
| Sep 22, 2011 at 8:30 | comment | added | Dr G | @DavidRoberts I should have phrased the question as a novel set in a universe where we know P=NP :) Re:Egan, I interpreted the story as a twist on intensional definition. Our theory is based on intensional definition, doesn't mean that the universe agrees, and since we haven't tried to verify the extensional version of our definitions the physical universe might disagree. | |
| Sep 22, 2011 at 7:40 | comment | added | David Roberts | ...and how do you know P=NP isn't true our universe? Let me know and I'll share the $1m with you. | |
| Sep 22, 2011 at 7:39 | comment | added | David Roberts | Dr G +1, but I'm not sure what versions of Egan's short stories you've read :P but I took it as being that truth values of arithmetic statements were behaving like the spin of a quantum particle, and the calculation of mathematical results was flipping these truth values, to the detriment of an 'other, parallel universe'. Physics itself was affected by changing the rules of maths, so there was chaos all-round when the 'others' fought back. (And yes, I have a PhD in pure maths) | |
| Sep 21, 2011 at 0:37 | answer | added | aquaherd | timeline score: 2 | |
| May 25, 2011 at 22:51 | answer | added | M.K. | timeline score: 5 | |
| May 23, 2011 at 2:37 | comment | added | grautur | Not a novel, but Russell Impagliazzo (a top complexity theory researcher) wrote a short paper describing five worlds in which such things happen (the Algorithmica universe has P = NP, Cryptomania has guaranteed public-key cryptography, etc.). Just thought I'd mention in case you're curious for a more theoretical viewpoint on what a world with P = NP would look like. blog.computationalcomplexity.org/2004/06/… | |
| Jan 28, 2011 at 15:16 | vote | accept | Dr G | ||
| Jan 28, 2011 at 14:45 | comment | added | Dan Geiser | The MathFiction Homepage would be a good starting point for something like this. | |
| Jan 13, 2011 at 16:16 | answer | added | Gelvis | timeline score: 1 | |
| Jan 13, 2011 at 7:20 | answer | added | Mike Scott | timeline score: 19 | |
| Jan 13, 2011 at 2:33 | answer | added | Martha F. | timeline score: 56 | |
| Jan 11, 2011 at 22:34 | comment | added | Dr G | Greg Egan wrote Dark integers and Luminous which are about calculability and complexity in a pure a algebra settings. If that can work, so can a novel about P=NP :) | |
| Jan 11, 2011 at 21:57 | history | edited | Dr G |
edited tags
|
|
| Jan 11, 2011 at 21:52 | comment | added | DampeS8N | for good reason, I'd imagine. I can see the dialogue right now. | |
| Jan 11, 2011 at 21:43 | history | asked | Dr G | CC BY-SA 2.5 |