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

Американский математик Мартин Дауд опубликовал решение одной из «задач тысячелетия» — доказательство неравенства классов сложности P и NP. За решение каждой из этих задач Математический институт Клэя назначил премию в миллион долларов США. В настоящее время научное сообщество изучает его результаты.

«Задачи тысячелетия» — это семь математических проблем, считающихся важными классическими задачами, которые оставались нерешенными в течение многих лет. За решение каждой из них Институт имени Клэя назначил вознаграждение в 1 млн долларов. До сих из «задач тысячелетия» была решена только одна — российский математик Григорий Перельман доказал гипотезу Пуанкаре, однако отказался от премии.

Теперь американский математик Мартин Дауд, сотрудник Hyperon Software, опубликовал решение еще одной «задачи тысячелетия». Он представил пятистраничное доказательство неравенства классов сложности P и NP. В настоящее время научное сообщество изучает его результаты, и об их достоверности судить пока рано.

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