Optiland

Many of you have heard of Russell Impagliazzo's five worlds from his 1995 classic A personal view of average-case complexity In short 

• Algorithmica: P = NP or something "morally equivalent" like fast probabilistic algorithms for NP. 
• Heuristica: NP problems are hard in the worst case but easy on average.
• Pessiland: NP problems hard on average but no one-way functions exist. We can easily create hard NP problems, but not hard NP problems where we know the solution. 
• Minicrypt: One-way functions exist but we do not have public-key cryptography.
• Cryptomania: Public-key cryptography is possible, i.e. two parties can exchange secret messages over open channels.

Impagliazzo's world has an explicit "you can't have your cake and eat it too", either you can solve NP-hard problems on average, or have cryptography but not both (neither is possible). That's the mathematical world of P v NP. 

The reality is looking more and more like Optiland, where we can solve difficult NP problems and still have cryptography thanks to vast improvements in machine learning and optimization on faster computers with specialized hardware.

Back in 2004 I gave my guess of the world of P = NP

Learning becomes easy by using the principle of Occam's razor--we simply find the smallest program consistent with the data. Near perfect vision recognition, language comprehension and translation and all other learning tasks become trivial. We will also have much better predictions of weather and earthquakes and other natural phenomenon.

Today you can take your smartphone, unlock it by having the phone scan your face, and ask it a question by talking and often get a reasonable answer, or have your question translated into a different language. You get alerts on your phone for weather and earthquakes, with far better predictions than we would have though possible a dozen years ago.

We have computed the shortest traveling-salesman tour through nearly 50K UK pubs. AlphaFold can simulate protein folding with an accuracy nearly as good as what we get with real-world experiments. You can view GPT-3 as generating a form of a universal prior. Even beyond P = NP, we have self-trained computers easily besting humans in Chess, Go and Poker.

Meanwhile these techniques have done little to break cryptographic functions. Plenty of cybersecurity attacks but rarely by breaking the cryptography. 

Not all is rosy--there is still much more we could do positively if P = NP  and we are already seeing some of the negative effects of learning such as loss of privacy. Nevertheless we are heading to a de facto best of both worlds when complexity theory tells us those worlds are incompatible.