Abstract

In 2013 I wrote a book chapter on an imagined world where P = NP. A world with advances in medicine, translation, video recognition and generation, and much more. With the advances we’ve seen in computing power, optimization, data-driven algorithms, and of course remarkable advances in artificial intelligence, much of this world is coming true. We’ve made dramatic progress on problems thought unsolvable a decade ago. With one major exception, our cryptographic protocols have remained secure.

How did we get to this seemingly impossible world I call Optiland where we can solve many difficult problems quickly in practice while our secrets remain secure, and what does it mean for our understanding and role of computational complexity?

We’ll give a (mostly) non-technical overview that takes a step back and rethinks complexity in light of these advances, what AI tells us about complexity, and what complexity tells us about AI.