Ryan Williams’s breakthrough result that ACC0 does not contain NEXP was announced on Richard Lipton’s blog on 8 November 2010.
This is exactly 3 months after a superficially similar announcement, Vinay Deolalikar’s attempt to show that P does not contain NP, which created unprecedented hubbub and excitement on the internet. (See my previous post P vs NP vs PR.)
Few researchers believed Deolalikar’s manuscript. By contrast, the result of Williams has been immediately welcomed with universal astonishment and respect. Our jaws collectively dropped. But they dropped in silence:
Internet attention does not seem to be a good way of measuring validity or relevance. There may be another message here about philosophy of science: Schopenhauer could hardly have been more wrong when he said,
All truth passes through three stages. First, it is ridiculed. Second, it is violently opposed. Third, it is accepted as being self-evident.
Now, back to reading Ryan’s paper. Silently.