100

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).

Improve this question
11
  • 12
    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, 2011 at 22:34
  • 8
    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, 2011 at 2:37
  • 30
    ...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, 2011 at 7:40
  • 3
    Maybe all of them... Since it's an unsolved problem at this moment. :-)
    – Brian Knoblauch
    Sep 28, 2011 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, 2012 at 0:12

10 Answers 10

Reset to default
56

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").

Improve this answer
0
81

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.

Improve this answer
13
  • 7
    +1 for using evidence from the world to show some thing. Most Excellent.
    – AncientSwordRage ♦
    Jan 5, 2012 at 10:46
  • 5
    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, 2012 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, 2012 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, 2012 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, 2013 at 8:53
26

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.

Improve this answer
19

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.

Improve this answer
7
  • 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, 2011 at 19:49
  • 3
    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 --- ex-moderator kitten
    Mar 19, 2011 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, 2011 at 22:06
  • 7
    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, 2011 at 17:36
  • 3
    @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, 2012 at 19:26
5

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.

Improve this answer
3
  • 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, 2012 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, 2012 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, 2015 at 18:15
3

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.

Improve this answer
1
  • "NP" in "P = NP" does not mean "not P", however. The phrasing could be based on a misunderstanding, but I'm sure the P vs. NP problem was not formulated by 1940, so they probably just meant to assert a contradiction ("P" being a generic proposition; by assuming P and not P, anything can follow.) AFAIK the P vs NP question was first posed as such in 1971.
    – Nick Matteo
    Feb 3, 2022 at 18:26
1

Nemesis, Isaac Asimov, 1989

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

Improve this answer
1
  • Please provide a date with your answer, next time and explain why this relates explicitly to P=NP.
    – AncientSwordRage ♦
    Feb 15, 2016 at 19:43
1

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.

Improve this answer
1
0

In the story Starshield Sentinels by Margaret Weis and Tracy Hickman, there were computers/artificial intelligences that could answer any question instantly by sending the question back in time to itself, giving it 'time' to solve it. The only hiccup to this was that the computer had to be 'awake' long enough to solve it (something like Deep Thought from The Hitchhiker's Guide to the Galaxy needing 10 million years to solve the question to life, the universe, and everything).

While I don't know if this exactly pertains to everything P = NP, it does solve the variable/solve clause in the question.

Of course the computers all go nuts and try to kill everyone in the story. Can't we stop trying to invent killer robots now?

Improve this answer
-2

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).

Improve this answer
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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