и что не врет?

http://www.hpl.hp.com/personal/Vinay_Deolalikar/
Это он. Понятно.
А где можно найти ссылку на сенсацию (кроме картинки)?

Сенсации нет, есть предлагаемое доказательство, которое он разослал в пятницу главным исследователям в области complexity.

там же есть линк на драфт
http://www.hpl.hp.com/personal/Vinay_Deolalikar/Papers/pnp_preliminary.pdf

Непохоже, что комментарий на HN написан специалистом.
К статфизике это доказательство отношения не имеет (почти). Мне объясняли, что все используемые автором приемы известны, но считалось, что доказательства на этом пути нет. Автор применяет некоторые технические новшества. Грубо говоря, есть некоторая вычислительная модель, про которую известно, что она строго слабее NP. Было известно, что эмулировать P в этой модели некоторым естественным образом нельзя. Автор предлагает хитрый неестественный и утверждает, что получается.
На самом деле, доказательство (если оно верно) доказывает больше, чем P!=NP. Видимо, из него должно следовать существование односторонней функции.

Я тоже думаю, что не специалистом - хотя бы потому, что я сам бы его мог написать :). Просто мне показалось, что он собирает вместе несколько тривиальных и базовых соображений, которые могут быть неочевидны кому-то, кто вообще не знает или с трудом знает, что это за P!=NP.

Спасибо за ваш комментарий, звучит очень интересно. Если узнаете еще что-то или увидите где-то дискуссию специалистов, буду благодарен за ссылку.

Наверное, завтра появится что-то в блоге Fortnow/Gasarch'а.

Криптографы перекрестились:)

:))

Так это, вроде ни factorization, ни descrete log не NP-complete. Чего креститься-то?

лиха беда начало

"О вас, математиках, говорят, как о сухарях" (~c)

"This is R.J. Lipton's blog post from today about this. To the unfamiliar, this is the blog of one of the leading researchers in the field, who is one of those who received the original email."

http://rjlipton.wordpress.com/2010/08/08/a-proof-that-p-is-not-equal-to-np/

Кончен бал, погасли свечи. http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/#comment-4754

увы.

Жалко.