Science Fiction & Fantasy Stack Exchange is a question and answer site for science fiction and fantasy enthusiasts. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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
10  
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
24  
...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
up vote 50 down vote accepted

Antibodies, Charles Stross, 2000

A short story 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

Star Trek, Various, 1966 (earliest occurrence)

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
4  
+1 for using evidence from the world to show some thing. Most Excellent. – AncientSwordRage Jan 5 '12 at 10:46
4  
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
1  
@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
    
@MichaelEdenfield: If there are problem solving techniques strictly more powerful than a very fast DTM, and for practical applications P and NP have lost relevance, that by itself is very strong evidence for P=NP in the universe. In a P!=NP universe the discovery of such techniques is very unlikely. – Tynam Sep 21 '13 at 8:53

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. – user56 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
5  
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
2  
@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
2  
+1 for HP & MoR :) – DVK-in-exile 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
6  
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
    
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. – zwol Dec 16 '15 at 18:15

Nemesis, Isaac Asimov, 1989

It talks about imposibilities and the implications of an universe where the laws of physics doesn't apply

share|improve this answer
    
Please provide a date with your answer, next time and explain why this relates explicitly to P=NP. – AncientSwordRage Feb 15 at 19:43

The Roaring Trumpet by Spague de Camp and Fletcher Pratt, published in May 1940 in Unknown. Here, psychologists posit that schizophrenics are actually mentally accessing alternate universes, and by applying the proper equations, one could travel to that alternate universe and bring the persons mind back to our universe. It was an intellectual exercise which the main protagonist Harold Shea decides to test out. He jokingly refers to travel via syllogismobile, but it involves studying and constructing the logic of the universe destination and reciting it out loud. This generally begins with "if P is equal to not P..." And goes from there. The entire Enchanter series has them universe hopping through mythology and fairy tale and classical works by doing so.

I suspect, never having given it any real thought, that by prefacing with P=NP, they were distinguishing the universe as one in which magic functions.

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? – AncientSwordRage Mar 29 '12 at 8:15

The practice effect, David Brin, 1984

This seems a likely candidate. In the depicted universe, a robotic probe from our universe starts to self-optimize both physically and mentally while the human intelligence remains unaltered. Also physical objects tend to self-optimize: a wooden sleigh develops lubricant to easily slide on the road. This practice effect can be boosted by a special state of trance where the solution appears immediately by itself, hence inanimate objects perform a wide-range evolution within non-polynomial time (Seeking a near infinite array of posible solutions within a short period of time). This universe actually transcends P=NP.

share|improve this answer
    
Please edit in why you think this is the case. – AncientSwordRage Feb 15 at 19:45

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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