P=NP Utopia

[ 04-06-2025 ] [ #cs ]

My Computational Complexity exam is next week. I should definitely be studying instead of writing this, but here I am, procrastinating in the most roundabout way: writing a random blog post that (probably) no one is going to read.

While skimming through Sanjeev Arora’s lecture notes, I stumbled upon this phrase:

If P = NP, then the world would be mostly a Utopia.

Has anyone ever turned that idea into a story? A world where P = NP? Think about it, there are plenty of short stories that act as vehicles for philosophical ideas (the ones that come to my mind are Le Guin’s “The Ones Who Walk Away from Omelas”, Chiang’s “Story of Your Life”, and practically anything that Borges ever wrote). But I can’t remember many that try to explore the consequences of results from Theoretical Computer Science – except for AI, I guess.

It would be fun to see a world where so many things would become feasable. The lack of digital privacy and Sudoku puzzles would definitely be weird, but it seems worth exploring.

Maybe I’ll write it one day. But before that, I should probably get back to studying.