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

Индийский математик заявил о решении "задачи тысячелетия"

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

Ученый опубликовал 100-страничную статью, в которой доказал, что классы сложности P и NP не равны.

Индийский математик Винай Деолаликар представил доказательства решения одной из "задач тысячелетия". Ученый опубликовал 100-страничную статью, в которой доказал, что классы сложности P и NP не равны. Препринт статьи в формате pdf можно скачать здесь. Коротко о работе написало издание New Scientist.

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

Доказательство, что классы сложности P и NP не равны, означает, что ответы на два вопроса, указанные выше, будут отрицательными. Иначе говоря, проверка шифра и его подбор - задачи разного класса сложности.

В настоящее время эксперты не имеют однозначного мнения по поводу статьи индийского ученого. Стоит ожидать, что оценки других математиков относительно строгости и правомерности доказательства увидят свет после того, как будет опубликован окончательный вариант статьи. Планируется, что это произойдет в течение недели.

Напомним, что задачи тысячелетия - это семь задач, за решение каждой из которых математический институт Клэя предлагает приз размером в один миллион долларов. В частности, одной из таких задач было доказательство гипотезы Пуанкаре. Приз за решение этой задачи был присужден российскому математику Григорию Перельману, который, однако, отказался от вознаграждения. Россиянин аргументировал свой отказ тем, что не согласен с решением института Клэя.

Больше новостей о: ИндияМатематика
По теме

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