?

Log in

No account? Create an account
математически-компьютерное - Поклонник деепричастий [entries|archive|friends|userinfo]
Anatoly Vorobey

[ website | Website ]
[ userinfo | livejournal userinfo ]
[ archive | journal archive ]

Links
[Links:| English-language weblog ]

математически-компьютерное [авг. 9, 2010|12:04 am]
Anatoly Vorobey
Неужели?

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

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

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

Comments:
[User Picture]From: shuriksprivetom
2010-08-08 09:14 pm
и что не врет?
(Ответить) (Thread)
[User Picture]From: meharher
2010-08-08 09:18 pm
http://www.hpl.hp.com/personal/Vinay_Deolalikar/
Это он. Понятно.
А где можно найти ссылку на сенсацию (кроме картинки)?
(Ответить) (Thread)
[User Picture]From: avva
2010-08-08 09:21 pm
Сенсации нет, есть предлагаемое доказательство, которое он разослал в пятницу главным исследователям в области complexity.
(Ответить) (Parent) (Thread) (Развернуть)
From: ionial
2010-08-09 04:42 am
(Ответить) (Parent) (Thread)
From: (Anonymous)
2010-08-08 09:48 pm
Непохоже, что комментарий на HN написан специалистом.
К статфизике это доказательство отношения не имеет (почти). Мне объясняли, что все используемые автором приемы известны, но считалось, что доказательства на этом пути нет. Автор применяет некоторые технические новшества. Грубо говоря, есть некоторая вычислительная модель, про которую известно, что она строго слабее NP. Было известно, что эмулировать P в этой модели некоторым естественным образом нельзя. Автор предлагает хитрый неестественный и утверждает, что получается.
На самом деле, доказательство (если оно верно) доказывает больше, чем P!=NP. Видимо, из него должно следовать существование односторонней функции.
(Ответить) (Thread)
[User Picture]From: avva
2010-08-08 09:58 pm
Я тоже думаю, что не специалистом - хотя бы потому, что я сам бы его мог написать :). Просто мне показалось, что он собирает вместе несколько тривиальных и базовых соображений, которые могут быть неочевидны кому-то, кто вообще не знает или с трудом знает, что это за P!=NP.

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

Наверное, завтра появится что-то в блоге Fortnow/Gasarch'а.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: zeroeight
2010-08-08 09:55 pm
Криптографы перекрестились:)
(Ответить) (Thread)
[User Picture]From: 0qwerty0
2010-08-08 11:15 pm
:))
(Ответить) (Parent) (Thread)
[User Picture]From: dimrub
2010-08-09 04:48 am
Так это, вроде ни factorization, ни descrete log не NP-complete. Чего креститься-то?
(Ответить) (Parent) (Thread) (Развернуть)
From: (Anonymous)
2010-08-09 07:58 am
лиха беда начало
(Ответить) (Parent) (Thread)
[User Picture]From: old_radist
2010-08-09 05:23 am
"О вас, математиках, говорят, как о сухарях" (~c)
(Ответить) (Thread)
From: (Anonymous)
2010-08-09 10:16 am

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

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

(Ответить) (Thread)
From: (Anonymous)
2010-08-10 10:10 pm
Кончен бал, погасли свечи. http://rjlipton.wordpress.com/2010/08/09/issues-in-the-proof-that-p%e2%89%a0np/#comment-4754
(Ответить) (Thread)
[User Picture]From: avva
2010-08-10 10:13 pm
увы.
(Ответить) (Parent) (Thread) (Развернуть)
[User Picture]From: ygam
2010-08-11 09:53 pm
Жалко.
(Ответить) (Parent) (Thread)