Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Fifty years of P vs. NP and the possibility of the impossible
Fortnow L., Fortnow L. Communications of the ACM65 (1):76-85,2021.Type:Article
Date Reviewed: Jun 27 2022

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.

Reviewer:  Jon Millen Review #: CR147460 (2208-0114)
1) Fortnow, L. The status of the P versus NP problem. Communications of the ACM 52, (2009), 78–86.
Bookmark and Share
  Editor Recommended
Featured Reviewer
Algorithms (B.2.4 ... )
Would you recommend this review?
Other reviews under "Algorithms": Date
Integer summing algorithms on reconfigurable meshes
Nakano K., Wada R. Theoretical Computer Science 197(1-2): 57-77, 1998. Type: Article
Dec 1 1998
Bit-level two’s complement matrix multiplication
Grover R., Shang W., Li Q. Integration, the VLSI Journal 33(1): 3-21, 2002. Type: Article
Oct 2 2003
 New approach to design for reusability of arithmetic cores in systems-on-chip
Margala M., Wang H. Integration, the VLSI Journal 38(2): 185-203, 2004. Type: Article
Aug 17 2005

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2023 ThinkLoud®
Terms of Use
| Privacy Policy