Sunday, August 8, 2010
Big news in complexity theory?
An HP researcher, Vinay_Deolalikar , is claiming to have proved that P != NP. This is of course a major result if correct. I would guess the odds are it isn't but an expert thinks it is worth taking seriously. I glanced through the preliminary version of the paper. It goes well beyond my superficial knowledge of complexity theory so I will defer to more expert opinion as to correctness. I expect this will be forthcoming fairly quickly.