Математики указали на возможные несоответствия в представленном Винэем Деолаликаром (Vinay Deolalikar) доказательстве того, что классы задач P и NP неравны.

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

Работа учёного пока не отправлена в научный журнал, и её обсуждение ведётся в блогах профессиональных математиков Ричарда Липтона (Richard Lipton) из Технологического института Джорджии и Скотта Ааронсона (Scott Aaronson) из ассачусетского технологического института. Поиск ошибок в доказательстве уже принёс результаты: г-н Липтон приводит замечания своих коллег Нила Иммермана (Neil Immerman) и Теренса Тао (Terence Tao), первыми обнаруживших серьёзные недочёты.

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

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