Решение задачи тысячелетия

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

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

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

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

По теме Решение задачи тысячелетия

Самовар третьего тысячелетия

Для русского быта и всего уклада жизни самовар значил гораздо больше, чем просто...
Журнал

Сонливость - эпидемия третьего тысячелетия

- Сонливость для современных людей - большая проблема, - рассказывает врач...
Журнал

Саммит тысячелетия-2

В Нью-Йорке вчера открылся трехдневный Саммит тысячелетия, посвященный итогам...
Журнал

Новая парадигма Нового мировоззрения Нового тысячелетия

Необычность Нового мировоззрения в том, что оно состоит из кубиков, паззлов...
Журнал

История человечества вплоть до 34 тысячелетия от РХ

Это послание является предсказанием будущих событий в истории человечества. Но...
Журнал

Задачи о купюрах и поездах

Задача о купюрах: • Существует 11 разных видов купюр. Все они разного номинала и...
Журнал

Опубликовать сон

Гадать онлайн

Пройти тесты

Популярное

Найти перо птицы: что сулит примета?
Как поступить с теми, кто причинил нам боль?