Примерное время чтения: 2 минуты
561

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

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

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

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

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

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

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

 

Смотрите также:

Оцените материал
Оставить комментарий (0)

Также вам может быть интересно

Топ 5 читаемых



Самое интересное в регионах