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

Индийский математик Винэй Деолаликар (Vinay Deolalikar) нашел доказательство решения одной из так называемых задач тысячелетия, сообщает Lenta.Ru. В 100-страничной статье ученый приходит к выводу, что классы сложности P и NP не равны.

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

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

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

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

Задачи тысячелетия — это семь задач, за решение каждой из которых математический институт Клэя предлагает приз размером в один миллион долларов. Одной из таких задач было доказательство гипотезы Пуанкаре. Приз за решение этой задачи был присужден российскому математику Григорию Перельману, который отказался от денег, объяснив свое решение несогласием с позицией института Клэя.

Подготовлено по материалам: www.livestream.ru