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.