Математики из разных стран мира усомнились в правомерности доказательства одной из задач тысячелетия - вопросе о неравенстве классов сложности P и NP. Препринт статьи (pdf), в которой доказывалось, что они не равны, представил в начале августа индийский математик Винэй Деолаликар (Vinay Deolalikar). Официально статья пока не подана в реферируемый научный журнал.
Деолаликар разослал препринт статьи нескольким ведущим математикам 6 августа 2010 года. Кроме того, по просьбе коллег ученый подготовил краткое описание своего доказательства и также выложил его в Сеть (pdf). Через несколько дней в блогах некоторых математиков появились записи, в которых они выражали сомнения в том, что Деолаликару действительно удалось строго доказать, что классы сложности P и NP не равны.
Так, сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон (Scott Aaronson) привел восемь причин, которые заставляют его думать, что Деолаликар не смог решить задачу тысячелетия. В частности, Ааронсон отмечает, что в своей статье Деолаликар не объясняет, почему его доказательство не работает для некоторых частных задач. Также ученый отмечает, что статья выдержана не в классическом стиле и в ней нет внятного краткого объяснения, почему новое доказательство смогло преодолеть барьеры, мешавшие математикам решить задачу тысячелетия раньше (такой обзор был дан в синопсисе, который Ааронсон, впрочем, считает малопонятным).
Также не уверен в том, что работа Деолаликара окончательно доказывает, что классы сложности P и NP не равны, Ричард Липтон (Richard Lipton), который, как и Ааронсон, является одним из крупнейших специалистов в области, к которой относится задача тысячелетия. В своем блоге Липтон перечисляет несколько недочетов в доказательстве Деолаликара, которые, с высокой вероятностью, делают его неправомерным.
Вопрос о равенстве или неравенстве классов сложности P и NP чрезвычайно важен для математики, а также для теории вычислений и наук о шифровании данных. Коротко эту проблему можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Например, перед человеком стоит задача составить кратчайший маршрут путешествия между несколькими городами. После того как маршрут составлен, можно легко проверить, действительно ли не существует более короткого пути, однако решить эту задачу (она относится к классу сложности NP) за небольшое время невозможно.
Если будет доказано, что классы сложности P и NP равны, то этот факт будет означать, что существует некий способ решить задачу о городах за разумное время (математики пользуются термином полиномиальное время). Подробнее прочесть о том, почему задача о равенстве классов сложности P и NP настолько важна (тот же Ааронсон обязался отдать Деолаликару 200 тысяч долларов, если его доказательство окажется верным), можно здесь.