Математик Деолаликар утверждает, что решил одну из «Задач тысячелетия» вслед за Перельманом

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

Данная проблема состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память), то есть действительно ли задачу легче проверить, чем решить?

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