Skip to content

P=NP Unresolved, Unlikely

There’s a great overview of the P=NP problem in the September issue of the Communications of the ACM.  If, like me, you’re behind on your CACM subscription and/or ACM membership, you can read the article online.  Author Lance Fortnow gives a broad view of the problem, the current approaches, the direction that research is headed, and even good descriptions of what’s at stake if the problem shakes out either way.

Also, despite his modest declaration in the introduction that the problem of P=NP is “still open” Fortnow’s overview gives strong support for the case that a better answer might be “probably not.”  There’s been no evidence that P=NP and increasingly good indications that such is simply not the case.

Fortnow also points out a lot of good current research on a variety of topics that are incidental to the P=NP problem.  All things considered, if you’re interested in the problem, the article is a must read.

Even if Fortnow DOES leave out my heuristics for addressing NP-Complete problems, Genetic Algorithms.(1)

1.)  Shameless self-promotion: for more on the work I did with the Gonzaga University Center for Evolutionary Algorithms on NP-Completeness and Genetic Algorithms, please see Trusses, NP-Completeness, and Genetic Algorithms.

Posted in Geekery.