Take the 2-minute tour ×
Science Fiction & Fantasy Stack Exchange is a question and answer site for science fiction and fantasy enthusiasts. It's 100% free, no registration required.

I wonder whether anyone has written a novel set in a universe where P=NP, in the event that there is more than one, which was the first?

enter image description here

In this universe all problems that could be verified in polynomial time (NP) (given the solution) could also be solved in polynomial time (P).

share|improve this question

closed as not constructive by Gilles Jul 26 '12 at 19:50

As it currently stands, this question is not a good fit for our Q&A format. We expect answers to be supported by facts, references, or expertise, but this question will likely solicit debate, arguments, polling, or extended discussion. If you feel that this question can be improved and possibly reopened, visit the help center for guidance.If this question can be reworded to fit the rules in the help center, please edit the question.

8  
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 :) –  Dr G Jan 11 '11 at 22:34
6  
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/… –  grautur May 23 '11 at 2:37
18  
...and how do you know P=NP isn't true our universe? Let me know and I'll share the $1m with you. –  David Roberts Sep 22 '11 at 7:40
3  
Maybe all of them... Since it's an unsolved problem at this moment. :-) –  Brian Knoblauch Sep 28 '11 at 15:38
2  
@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. –  Kyle Jones Jan 7 '12 at 0:12

8 Answers 8

up vote 41 down vote accepted

Charles Stross wrote a short story called "Antibodies" that hinges on the fact that solving P=NP is a required prerequisite for developing a computer intelligence. It's available in his book Toast. Stross has put the full text of this book online. (This link will take you directly to the story.)

And according to Stross's site, the story was:

Published in Interzone #157; republished in "The Year's Best Science Fiction #18" (ed. Gardner Dozois). Mentioned in Locus' "Recommended Reading List" for 2000. Shortlisted for the 2001 Theodore Sturgeon Award (lost to Ian MacDonald's "Tendoleo's Story").

share|improve this answer

P=NP in the Star Trek universe, but the people there aren't aware of it. Evidence:

  1. There is encryption but it is always breakable. P=NP will let you crack everything but one-time pads but the Federation stubbornly continues to use NP-based ciphers.

  2. The efficacy of the universal translator. P=NP would make learning new languages a breeze, at least for a computer. Learning systems would be so simple and straightforward to implement that there wouldn't be a linguist left with a job.

  3. The efficacy of the bio-filter. The transporter routinely filters unknown organisms, viruses and other hazards when crewmen are beamed aboard ship. But "bio-filter" is a misleading term as it brings to mind some sort of sieve that catches all the bad stuff and passes only the good. In reality running such a "filter" over transport data would be the mother of all induced subgraph isomorphism problems, as you would have to identify all virus-sized structures in an organism chock-full of such structures. P=NP magicks away the input-related exponent that makes such problems intractable even for small graphs.

  4. Self-aware machine intelligence is created with ease. Wesley Crusher created one by accident. So did Richard Daystrom. The Enterprise D computer cooked up Moriarty in its spare cycles, Dr. Farallon created the Exocomps, and so on. All you seem to need to do is build something equivalent to a theorem proving system and let it run long enough to stumble over the proof that P or some other tractable class is equivalent to NP and the system is off to the races.

Or perhaps the Star Trek denizens are collapsing the polynomial hierarchy by technological means. The Federation, Borg, etc. seem to have ready access to time machines, wormholes, exotic matter, and superluminal signalling, so they could be using closed time-like curves for computation. This according to Scott Aaronson would allow them efficiently solve PSPACE-complete problems.

share|improve this answer
3  
+1 for using evidence from the world to show some thing. Most Excellent. –  Pureferret Jan 5 '12 at 10:46
3  
I think they merely tackle the three points you issue by raw computing power. A DTM can solve precisely the same problems as an NTM, but it takes longer. So, if their engineering skills are mad enough, they can cough up really fast (parallel) computers (also they probably found a couple of nice heuristics for some NP-hard problems along the way). So, I'm not sure how your arguments apply. –  bitmask Feb 11 '12 at 20:20
    
@Blue Perhaps I should have written P=NP lets you crack everything useful but one-time pads. If you can't verify decryption in polynomial time, which is what having a cryptosystem outside NP means, then even with the key decryption is not computationally feasible. That to me is not a useful cryptosystem. –  Kyle Jones May 14 '12 at 21:15
    
@bitmask +1. It's more likely, IMO, that the Star Trek universe has mastered problem solving techniques that are strictly more powerful than a DTM (they can replicate the action of the human brain, for example). It you aren't restricted to what a DTM can solve, then for practical applications P and NP lose their relevance. –  Michael Edenfield May 17 '12 at 17:27
    
@bitmask: It's somewhere in the Tech Manuals that Star Trek runs the computer core inside a modified warp field where time runs at a different rate. –  Zan Lynx Nov 18 '12 at 21:38

The other Stross book that deals with this is The Atrocity Archives, where Alan Turing solved P=NP, but they then found that doing so allowed access to the Cthonic Realms, so now an entire branch of Government exists to prevent this discovery becoming public knowledge.

share|improve this answer

In Vernor Vinges "Zones of Thought" series ("The Blabber", A Fire Upon the Deep, A Deepness in the Sky and the forthcoming The Children of the Sky), computation is easier in some parts of the galaxy, allowing for things like artificial intelligence and FTL travel.

It has been speculated (but there's no direct evidence in the books) that P=NP in these zones.

share|improve this answer
    
Is there any indirect evidence? My recollection is that computation is different outside the Slow Zone (Church's thesis only holds in the Slow Zone) and something like P=NP needn't apply or even make sense there. –  Gilles Jan 13 '11 at 19:49
1  
In A Fire Upon the Deep the Skode Riders find Pham's belief in public key encryption to be humorous. From that we can conclude that P == NP in the Beyond. –  dmckee Mar 19 '11 at 21:38
1  
Not necessarily -- quantum computers could theoretically handle NP-complete problems in polynomial time, even without P=NP. –  Mike Scott Mar 19 '11 at 22:06
4  
No, they cannot. The operations that the most widespread public-key encryption algorithms rely on being difficult - factoring, discrete log - are not (believed to be) NP-complete. These are the problems that quantum computers are theoretically able to break in polynomial time. That being said, there are public-key encryption algorithms that are based on NP-complete problems, but these are not in widespread use (yet...) –  BlueRaja - Danny Pflughoeft May 3 '11 at 17:36
1  
@BlueRaja We currently know no way to use a quantum computer to solve NP complete problems efficiently, but you're asserting that P < NP <= BQP is false, and I know of no proof for this. I agree that it's likely false, but you state it as a fact. –  CodesInChaos Jan 14 '12 at 19:26

In the fanfic Harry Potter and the Methods of Rationality by Eliezer S. Yudkowsky, Harry gets a time machine and tries to factor the product of two large prime numbers using this machine, with a somewhat weird result. So it is not completely given that NP=P, but seems probable.

share|improve this answer
    
+1 for HP & MoR :) –  DVK Jan 14 '12 at 18:48
    
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. –  Tadeusz A. Kadłubowski Jun 6 '12 at 8:51
2  
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'. –  M.K. Jun 8 '12 at 10:51

Nemesis, From Isaac Asimov talks about imposibilities and the implications of an universe where the laws of physics doesn't apply

share|improve this answer

If I'm not mistaken, in Bob Shaw's 'The Ragged Astronauts', one of the characters spends a bit of time explaining how pi is 3 to another. If pi is 3, I can only imagine what the rest of the physics is like. (I only remember the scene at all because the whole scene was a bit out of place, which was pretty unusual for the book - otherwise it was a neat tale).

share|improve this answer
    
How does this relate to p=np? –  Pureferret Mar 29 '12 at 8:15

"The practice effect" by David Brin seems a likely candidate.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.