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.  Communications of the ACM 65 (1): 76-85, 2022. 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
Algorithms (B.2.4 ... )
Would you recommend this review?
Other reviews under "Algorithms": Date
Efficient resource sharing algorithm for physical register file in simultaneous multi-threading processors
Zhang Y., Lin W.  Microprocessors & Microsystems 45, Part B, 270-282, 2016. Type: Article
Nov 9 2016
SRT division algorithms as dynamical systems
McCann M., Pippenger N.  SIAM Journal on Computing 34(6): 1279-1301, 2005. Type: Article
Feb 23 2006
 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 © 2000-2022 ThinkLoud, Inc.
Terms of Use
| Privacy Policy