Индийский математик заявил о решении одной из так называемых задач тысячелетия. Ученый Винэй Деолаликар (Vinay Deolalikar)опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны.
Индийский математик заявил о решении одной из так называемых задач тысячелетия. Ученый Винэй Деолаликар (Vinay Deolalikar)опубликовал 100-страничную статью, в которой сделан вывод, что классы сложности P и NP не равны.
Вопрос о равенстве классов сложности P и NP можно сформулировать так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти? Эта задача чрезвычайно важна для компьютерных вычислений и прикладных наук, в частности для наук о шифровании данных. Например, если можно быстро проверить, является ли введенный шифр правильным, то можно ли достаточно быстро взломать этот шифр?
Представленное индийским математикам доказательство задачи тысячелетия означает, что ответы на представленные выше два вопроса будут отрицательными. То есть проверка шифра и его подбор являются задачами разного класса сложности.
В настоящее время экспертное сообщество не вынесло однозначного мнения по поводу статьи Деолаликара. Оценки других математиков относительно строгости и правомерности доказательства начнут появляться после того, как будет опубликован окончательный вариант статьи, передает Лента.ру. Планируется, что это произойдет в течение недели.
За решение одной из задач тысячелетия математический институт Клэя предлагает приз размером в один миллион долларов. Всего существует семь задач. Одной из них было доказательство гипотезы Пуанкаре. Приз за решение этой задачи был присужден российскому математику Григорию Перельману. Однако он отказался от премии в 1 миллион долларов. Главной причиной своего отказала ученый назвал несогласие с организованным математическим сообществом.
