Миллион долларов за решение задачи тысячелетия. Украинский ученый может получить рекордную премию американского математического института Клэя за решение одной из семи математических проблем, решение которых ищут последние 30 лет.
Речь идет о задаче P и NP.
В теории алгоритмов вопрос о равенстве классов сложности P и NP является одной из центральных открытых проблем уже более трех десятилетий. Если на него будет дан утвердительный ответ, это будет означать, что теоретически возможно решать многие сложные задачи существенно быстрее, чем сейчас.
В конечном счёте проблема P = NP состоит в следующем: если положительный ответ на какой-то вопрос можно быстро проверить (за полиномиальное время), то правда ли, что ответ на этот вопрос можно быстро найти (за полиномиальное время и используя полиномиальную память)?
Неформально говоря, действительно ли решение задачи легче проверить, нежели отыскать?
Свой вариант решения луганский ученый опубликовал в Международном научном журнале. Сейчас его проверяют специалисты. Если решение окажется правильным и премию выплатят, Анатолий Плотников потратит ее на покупку квартиры. Ведь он, хоть и профессор, но до сих пор живет в комнате университетского общежития.
Видео: Подробности
Профессор из Луганска, возможно, решил одну из "задач тысячелетия" (видео)
20 сентября 2012 19:56