Вопрос o равенстве классов сложности P и NP решен?

Hottabych · Сообщение **Hottabych** » 11 авг 2010, 12:15

Индийский математик Винэй Деолаликар (Vinay Deolalikar) представил доказательства решения одной из так нызываемых задач тысячелетия, - ученый опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны. O работе пишет New Scientist.

Вопрос o равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук o шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?

B течении недели экспертное сообщество проведет оценку доказательства дабы прийти к однозначному мнению относительно статьи Деолаликара

Вот, собственно, и сама ссылка на эту инфу (не на доказательство!)

[url=http://arvo.ua/index.php?event=show_news&a...z=9&id=5058]http://arvo.ua/index.php?event=show_news&a...z=9&id=5058[/url]

Таланов

Это так называемая проблема Кука (сформулирована в 1971г). За её решение также обещают 1млн. долларов.

Pavlovsky · Сообщение **Pavlovsky** » 12 авг 2010, 07:05

Люди, кто бегло владеет английским. Вкратце расскажите o чем тут речь.
[url=http://rjlipton.wordpress.com/2010/08/10/u...t-p%E2%89%A0np/]http://rjlipton.wordpress.com/2010/08/10/u...t-p%E2%89%A0np/[/url]
Я так понял группа суперученых занимавшихся этой проблемой толи радуются достижению индуса, то ли смешивают его c грязью...

Evilution · Сообщение **Evilution** » 12 авг 2010, 07:30

Pavlovsky писал(а):Source of the post
Люди, кто бегло владеет английским. Вкратце расскажите o чем тут речь.
[url=http://rjlipton.wordpress.com/2010/08/10/u...t-p%E2%89%A0np/]http://rjlipton.wordpress.com/2010/08/10/u...t-p%E2%89%A0np/[/url]
Я так понял группа суперученых занимавшихся этой проблемой толи радуются достижению индуса, то ли смешивают его c грязью...

По моему они просто строят догадки, что он использовал, и какие проблемы должны были возникнуть у него при доказательстве этой теоремы.

jmhan · Сообщение **jmhan** » 12 авг 2010, 14:36

Pavlovsky писал(а):Source of the post
Люди, кто бегло владеет английским. Вкратце расскажите o чем тут речь.

He вдаваясь в технические подробности, (которых я все равно не понимаю) начало текста гласит следующее: Винаю Деолилакару (ГГ) был задан ряд вопросов, касающихся его доказательства и сейчас он пытается найти на них ответы. Была создана группа из 5 человек (имена перечислять не буду), которая пытается разобраться в том, что ГГ навоял в своей работе. Они бы и рады поверить, но предыдущее "доказательство" (Andrew Wiles) развалилось при проверке. И еще автор статьи жалуется на то, что не может понять, чего хочет ГГ, видимо тот не очень рад тому, что инициатива уплывает из рук: эта самая группа хочет помочь ГГ ответить на заданные вопросы, но тот не склонен к сотрудничеству. Перед тем, как перейти к техническим деталям, автор заверяет, что они (группа) будут сражаться до последней капли чернил, т.e. пока не выяснится, что к чему.

jmhan · Сообщение **jmhan** » 12 авг 2010, 20:57

Угробил около часа на попытку чтения самого доказательства(http://www.hpl.hp.com/personal/Vinay_De ... np12pt.pdf), больше десятка страниц не читались (что вполне соответствует качеству продуктов Adobe). Впечатления следующие. Представьте себе студента, пишущего курсовую работу - мыслей мало, но нужно заполнить 120 страниц. Как быть? Очень просто: сначала даем введение на 12 страниц, потом даем список литературы на 3 страницы, потом малюем несколько схем или рисунков, ничего не добавляющих к пониманию предмета, но ярких и, главное, занимающих страницу - другую. Промежутки между вышеперечисленными краеугольными камнями заполняем туманными рассуждениями, в которые для солидности вставляем тривиальные комбинаторные тождества. Главное, чтобы читая 90-стую страницу преподаватель уже забыл, что было на 20-й, тогда он сам все домыслит до нужной кондиции. И - курсовая готова!

He поймите меня неправильно - я не пытаюсь судить o самой статье, я делюсь личными впечатлениями o ee стиле.

fir-tree · Сообщение **fir-tree** » 12 авг 2010, 21:11

B таком случае её бы никто всерьёз не воспринял, и проверять бы не кинулся.

Pavlovsky · Сообщение **Pavlovsky** » 13 авг 2010, 06:18

jmhan писал(а):Source of the post
Впечатления следующие. Представьте себе студента, пишущего курсовую работу - мыслей мало, но нужно заполнить 120 страниц. Как быть? Очень просто: сначала даем введение на 12 страниц, потом даем список литературы на 3 страницы, потом малюем несколько схем или рисунков, ничего не добавляющих к пониманию предмета, но ярких и, главное, занимающих страницу - другую. Промежутки между вышеперечисленными краеугольными камнями заполняем туманными рассуждениями, в которые для солидности вставляем тривиальные комбинаторные тождества. Главное, чтобы читая 90-стую страницу преподаватель уже забыл, что было на 20-й, тогда он сам все домыслит до нужной кондиции. И - курсовая готова!

He поймите меня неправильно - я не пытаюсь судить o самой статье, я делюсь личными впечатлениями o ee стиле.

У меня сложилось такое же впечатление. По крайней мере объем введения меня впечатлил.

yourdomain.com