Star Trek, Various, 1966 (earliest occurrence) P=NP in the Star Trek universe, but the people there aren't aware of it.
Evidence:
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.
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.
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.
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.
scifi.stackexchange.com/users/4096/Kyle Jones
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").
scifi.stackexchange.com/users/69/Martha F.
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.
scifi.stackexchange.com/users/2213/deworde
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.
scifi.stackexchange.com/users/23/Mike Scott
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.
scifi.stackexchange.com/users/2409/M.K.
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.
scifi.stackexchange.com/users/24024/Broklynite
Nemesis, Isaac Asimov, 1989
It talks about imposibilities and the implications of an universe where the laws of physics doesn't apply
scifi.stackexchange.com/users/149/Gelvis
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.
scifi.stackexchange.com/users/2818/aquaherd
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?
scifi.stackexchange.com/users/103315/jersey
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?   In this universe all problems that could be verified in polynomial time (NP) (given the solution) could also be solved in polynomial time (P).
Which was the first novel set in universes where P=NP?
scifi.stackexchange.com
<history-of><hard-sci-fi><mathematics>
scifi.stackexchange.com/questions/43
scifi.stackexchange.com/users/50/Dr G
Works set in universes where P=NP are said to include The Practice Effect, by David Brin (1984); Antibodies (2000) and The Atrocity Archives, by Charles Stross (2000). P=NP in the Star Trek Universe in 1966. There are 3 possibilities for where  the first novel was set in universes where P=NP - 'Star Trek Various 1966, 'Antibodies' by Charles Stross 2000, and 'The Practice Effect by David Brin 1984.
There are 3 possibilities for where  the first novel was set in universes where P=NP - 'Star Trek Various 1966, 'Antibodies' by Charles Stross 2000, and 'The Practice Effect by David Brin 1984.