editor’s;letter
DOI: 10.1145/1839676.1839677
Moshe;Y.;Vardi
on P, nP, and
computational complexity
The second week of August was an exciting
week. On Friday, August 6, Vinay Deolalikar
announced a claimed proof that P ≠ NP.
Slashdotted blogs broke the news on
August 7 and 8, and suddenly the whole
world was paying attention. Richard
Lipton’s August 15 blog entry at blog@
CACM was viewed by about 10,000
Moshe Y. Vardi, EdIToR-In-CHIEF