математически-компьютерное

[avva]

Неужели?

(относительно серьезный кандидат на доказательство P!=NP)

(автор - не шарлатан. Реакций экспертов пока нет, читают. Он разослал док-во в пятницу. Док-во использует методы статистической физики)

(некоторые известные факты и элементарные соображения хорошо подытожены в комментарии на HN).

Comments

[shuriksprivetom.livejournal.com]

и что не врет?

[meharher.livejournal.com]

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

[avva.livejournal.com]

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

[http://users.livejournal.com/d_m_/]

Если в конце концов с доказательством согласятся, это и будет сенсация. Насколько я помню, в отличие от БТ Ферма, ответ на вопрос о равенстве/неравенстве P и NP имеет практическое значение (лучше бы он, конечно, равенство доказал).

[michk.livejournal.com]

Вроде особого практического значения нет, если не равны.

[avva.livejournal.com]

Я не уверен, что док-во неравенства имеет практическое значение, но это (если это док-во подтвердится), конечно, огромная сенсация.

[http://users.livejournal.com/d_m_/]

Согласен. Я сформулировал неудачно. Имелось в виду, что от доказательства БТФ, равно как и от контрпримера против БТФ никому ни тепло, ни холодно. В данном случае либо меняется взгляд на многие вещи (если P==NP, особенно если доказательство поясняет, как сводить NP алгоритмы к P), либо мы хороним робкие надежды (если NP!=P).

[blacklion.livejournal.com]

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

[http://users.livejournal.com/d_m_/]

Ок, можно и так сформулировать.
Хотя, есть же области, где алгоритм сведения открыл бы новые горизонты, где нужно, чтобы не подольше, а побыстрее :)

[alexeybobkov]

Параноики всё равно будут подозревать, что спецслужбы подделали доказательство :)

[(Anonymous)]

Прелесть БТФ не в том, что она дала какой-то результат, а в том, что она потребовала развития потрясающего математического аппарата для своего решения. И эти она ценна.

[http://users.livejournal.com/d_m_/]

Разумеется, Вы правы. Я имел в виду, что сама по себе формулировка БТФ (либо её отрицание) как результат бесполезен.

[ionial.livejournal.com]

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

[(Anonymous)]

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

[avva.livejournal.com]

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

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

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

[(Anonymous)]

Простой поиск (Яндексом :) дает такую ссылку http://yvl.livejournal.com/14141.html
Кажется, там есть человек, которому можно задавать вопросы

[cema.livejournal.com]

А Gasarch это тот, кто в Мэриленде? Любопытно.

[http://users.livejournal.com/girly_girl_/]

Scott Aaronson делает ставку:
http://scottaaronson.com/blog/?p=456

[zeroeight.livejournal.com]

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

[0qwerty0.livejournal.com]

:))

[dimrub.livejournal.com]

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

[(Anonymous)]

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

[zeroeight.livejournal.com]

Может я путаю, но с factorization не все так просто, нет четкой позиции насчет NP-Completeness.

[old-radist.livejournal.com]

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

почерпнуто из общего источника

[(Anonymous)]

"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/

[(Anonymous)]

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

[avva.livejournal.com]

увы.

ahem ...

[ded-maxim.livejournal.com]

http://rjlipton.wordpress.com/2010/08/10/update-on-deolalikars-proof-that-p%E2%89%A0np/

а вот это уже серьезные возражения

[ded-maxim.livejournal.com]

http://rjlipton.wordpress.com/2010/08/12/fatal-flaws-in-deolalikars-proof/

[ygam.livejournal.com]

Жалко.