подписаться на рассылку
26.5 26.9
28.3 28.7
  • 0
  • 0

Математики засомневались в правильности решения "задачи тысячелетия"

Винай Деолаликар.
Винай Деолаликар.

Сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон привел восемь причин, которые заставляют его думать, что Деолаликар не смог решить задачу тысячелетия.

Ученые-математики со всего мира сомневаются в правомерности доказательства одной из задач тысячелетия - вопросе о неравенстве классов сложности P и NP. Напомним, что препринт статьи, в которой доказывалось, что они не равны, представил в начале августа 2010 года индийский математик Винэй Деолаликар. Впрочем, пока статья не подана в реферируемый научный журнал.

Как стало известно, Деолаликар разослал препринт статьи нескольким ведущим математикам 6 августа 2010 года. Также, по просьбе коллег ученый подготовил краткое описание своего доказательства и выложил его в Интернет. Однако спустя несколько дней в блогах некоторых математиков появились записи, в которых они выражали сомнения в том, что Деолаликару действительно удалось строго доказать, что классы сложности P и NP не равны.

В частности, сотрудник Массачусетского технологического института (MIT) Скотт Ааронсон привел восемь причин, которые заставляют его думать, что Деолаликар не смог решить задачу тысячелетия. По словам Ааронсона, в своей статье Деолаликар не объясняет, почему его доказательство не работает для некоторых частных задач. Также ученый отмечает, что статья выдержана не в классическом стиле и в ней нет внятного краткого объяснения, почему новое доказательство смогло преодолеть барьеры, мешавшие математикам решить задачу тысячелетия раньше.

Также сомневается в правильности решения задачи и  Ричард Липтон, который, как и Ааронсон, является одним из крупнейших специалистов в области, к которой относится задача тысячелетия. В своем блоге Липтон перечисляет несколько недочетов в доказательстве Деолаликара, которые, с высокой вероятностью, делают его неправомерным.

Следует отметить, что вопрос о равенстве или неравенстве классов сложности P и NP чрезвычайно важен для математики, а также для теории вычислений и наук о шифровании данных. Вкратце задача звучит так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Например, перед человеком стоит задача составить кратчайший маршрут путешествия между несколькими городами. После того как маршрут составлен, можно легко проверить, действительно ли он является самым коротким, однако решить эту задачу (она относится к классу сложности NP) за небольшое время невозможно.

По теме

Архив
Новости