denis_balin (denis_balin) wrote,
denis_balin
denis_balin

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

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

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

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

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

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

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

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

Подробнее: http://news.mail.ru/society/4295126/
Subscribe
promo denis_balin april 27, 2016 07:00 197
Buy for 300 tokens
Всем привет! Сегодня опубликую стандартный пост для любого туриста, который приезжает в Петербург. Посещение такого места обязательно входит в программу. Поэтому, я понимаю, сколько они делают при этом фотографий, каждый метр таких мест кем-нибудь, да заснят. Так что, вряд ли Вы увидите в этом…
  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 0 comments