A Most Profound Math Problem

On August 6, 2010, a computer scientist named Vinay Deolalikar published a paper with a name as concise as it was audacious: “$P ≠ NP$.” If Deolalikar was right, he had cut one of mathematics’ most tightly tied Gordian knots. 

In 2000, the P = NP problem was designated by the Clay Mathematics Institute as one of seven Millennium Problems—“important classic questions that have resisted solution for many years”—only one of which has been solved since. (The Poincaré Conjecture was vanquished in 2003 by the reclusive Russian mathematician Grigory Perelman, who refused the attached million-dollar prize.

Read more »