Mail.RuПочтаМой МирОдноклассникиИгрыЗнакомстваНовостиПоискВсе проекты
17 августа 2010, источник: Аргументы и факты

Математик, решивший «задачу тысячелетия», ошибся

Винэй Деолаликар, по мнению его коллег, представил некорректное доказательство двух классов задач

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

Его метод вызвал критику коллег: профессиональных математиков Ричарда Липтона из Технологического института Джорджии и Скотта Ааронсона из Массачусетского технологического института. Результаты поиска ошибок они представили в своих блогах, сообщает Компьюлента.

В частности, Липтон приводит замечания своих коллег Нила Иммермана и Теренса Тао.

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

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

Винэй Деолаликар надеется исправить этот и другие недочёты. В настоящее время он готовит «полный вариант» публикации – 121 страницу математических выкладок.

Пока ни одного комментария, будьте первым!
Чтобы оставить комментарий, вам нужно авторизоваться.
, вы можете комментировать еще  дней
, вы можете комментировать еще  дней
31 день подписки от 59 рублей
Оплатить подписку