В решении "задачи тысячелетия" найдены несоответствия

Автор: Mega
Просмотров: 1868
Комментариев: 0
Дата: 17-08-2010, 19:39
В решении "задачи тысячелетия" найдены несоответствия
В решении "задачи тысячелетия" найдены несоответствия Математики указали на возможные несоответствия в представленном Винэем Деолаликаром доказательстве того, что классы задач P и NP неравны.
К классу P возможно отнести те вычислительные задачи, которые (условно) без труда решаются, а в группу NP входят задачи, решение которых без труда проверить. Неравенство классов P и NP лежит в основе популярных криптографических алгоритмов.
В решении "задачи тысячелетия" найдены несоответствия Математики указали на возможные несоответствия в представленном Винэем Деолаликаром доказательстве того, что классы задач P и NP неравны.

К классу P возможно отнести те вычислительные задачи, которые (условно) без труда решаются, а в группу NP входят задачи, решение которых без труда проверить. Неравенство классов P и NP лежит в основе популярных криптографических алгоритмов.

Своё подтверждение сотрудник Исследовательской лаборатории Hewlett-Packard в Пало-Альто Винэй Деолаликар опубликовал на прошлой неделе.

Работа учёного пока не отправлена в научный журнал, и её обсуждение ведётся в блогах профессиональных математиков Ричарда Липтона из Технологического института Джорджии и Скотта Ааронсона из Массачусетского технологического института.

Поиск ошибок в доказательстве уже принёс результаты: Липтон приводит замечания своих коллег Нила Иммермана и Теренса Тао, I-ми обнаруживших солидные недостатки.

В собственном письме Иммерман обращает внимание на то, что Винэй Деолаликар, пытаясь продемонстрировать, что отдельные трудности входят в класс NP, однако не попадают в Р, нарушает правила "обращения" с набором FO(LFP). Комментарий Теренса Тао касается задачи выполнимости булевых формул, при использовании которой в доказательстве, по заключению учёного, к тому же были допущены ошибки.

В блоге Скотта Ааронсона, с самого начала настроенного вполне критически, приводится целый перечень претензий. В т.ч., Аронсон указывает на то, что в материале Деолаликара не объясняется, по какой причине подтверждение не работает в случае некоторых вариаций NP-полных проблем, входящих в класс Р. Иные вопросы Ааронсона относятся к построению подтверждения и стилю изложения.

Винэй Деолаликар, хотя, ещё полагается поправить этот и иные недостатки, указывает "Компьюлента". Сейчас он готовит "полный вариант" публикации, которая отправится на рассмотрение в журнал; объём текущей версии подтверждения, содержащей отдельные исправления, уже вырос до 121 страницы.

Научно-популярное онлайн издание "Меганаука"