The P versus NP problem is one of the most fundamental and well-known unresolved questions in computer science. In comparison with the 2009 Communications article by the same author [1], the current survey is less about progress toward a solution and more about how to live with it unsolved. We may hope for an “Optiland” world with adequate success when it comes to the apparently incompatible goals of solving hard NP problems and having secure cryptography, due to advances in machine learning and other areas.

About a third of the article is about the advances, applications, and limits of machine learning. The connection to P versus NP is not obvious, but it exists: if P = NP, a polynomial-time algorithm can find the minimal boolean circuit that exactly matches a training database. But the story does not end here. Deep learning can deliver a neural net that is good enough and more efficient to run. And neither approach solves important side issues such as explainability and robustness.

This sort of nuanced and holistic analysis is carried out for several computational approaches and applications. Plenty of attention is given to quantum computing, circuit complexity, geometric complexity, and other optimization advances, with up-to-date results and references. Nonspecialists will appreciate the introductory material and broad coverage of this survey, and perhaps especially enjoy the provocative, bold predictions about the consequences, or lack thereof, of a P versus NP result.