"So, if we were to draw a map of the complexity class NP according to current knowledge, what would it look like? There’d be a huge, growing component of NP-complete problems, all connected to each other by an intricate network of reductions. There’d be a second huge component of P problems, many of them again connected by reductions. Then, much like with the map of the continental US, there’d be a sparser population in the middle: stuff like factoring, graph isomorphism, and Unique Games that for various reasons has thus far resisted assimilation onto either of the coasts.
"Of course, to prove P=NP, it would suffice to find a single link—that is, a single polynomial-time equivalence—between any of the tens of thousands of problems on the P coast, and any of the tens of thousands on the NP-complete one. In half a century, this hasn’t happened: even as they’ve both ballooned exponentially, the two giant regions have remained defiantly separate from each other. But that’s not even the main point. The main point is that, as people explore these two regions, again and again there are “close calls”: places where, if a single parameter had worked out differently, the two regions would have come together in a cataclysmic collision. Yet every single time, it’s just a fake-out. Again and again the two regions “touch,” and their border even traces out weird and jagged shapes. But even in those border zones, not a single problem ever crosses from one region to the other. It’s as if they’re kept on their respective sides by an invisible electric fence."