Деолаликар, сотрудник Исследовательской лаборатории Hewlett-Packard в Пало-Альто, доказал неравенство задач классов P и NP. К классу P относятся те вычислительные задачи, которые (условно) легко решаются, а в группу NP входят задачи, решение которых легко проверить. Неравенство классов P и NP лежит в основе популярных криптографических алгоритмов.
Его метод вызвал критику коллег: профессиональных математиков Ричарда Липтона из Технологического института Джорджии и Скотта Ааронсона из Массачусетского технологического института. Результаты поиска ошибок они представили в своих блогах, сообщает Компьюлента.
В частности, Липтон приводит замечания своих коллег Нила Иммермана и Теренса Тао.
Иммерман обращает внимание на то, что Винэй Деолаликар, пытаясь показать, что некоторые проблемы входят в класс NP, но не попадают в Р, нарушает правила «обращения» с набором FO(LFP). Комментарий Теренса Тао касается задачи выполнимости булевых формул, при использовании которой в доказательстве, по мнению ученого, также были допущены ошибки.
В блоге Скотта Аронсона говорится, что Деолаликар не объясняет, почему доказательство не работает в случае некоторых вариаций NP-полных проблем (скажем, задачи выполнимости булевых формул в 2-конъюнктивной нормальной форме), входящих в класс Р.
Винэй Деолаликар надеется исправить этот и другие недочёты. В настоящее время он готовит «полный вариант» публикации – 121 страницу математических выкладок.
