Американский математик индийского происхождения Винай Деолаликар утверждает, что решил одну из так называемых «Задач тысячелетия». Как сообщает New Scientist, ученый опубликовал на сайте препринтов доказательство неравенства классов сложности P и NP.
Данная проблема состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память), то есть действительно ли задачу легче проверить, чем решить?
«Задачи тысячелетия» представляют собой семь математических проблем, охарактеризованных как «важные классические задачи, решение которых не найдено в течение многих лет», и за решение каждой из этих проблем Институтом имени Клэя назначен приз в $1 млн. К настоящему моменту была присуждена только одна премия. За доказательство гипотезы Пуанкаре премия была присуждена российскому математику Григорию Перельману, но он 1 июля отказался от этой премии.
