Всего существует 7 задач, за которые объявлен столь большой приз. На данный момент только одна из семи проблем (гипотеза Пуанкаре) решена Григорием Перельманом, который отказался от приза в миллион долларов, а также от получения Филдсовской премии, которая вручается один раз в 4 года молодым математикам не старше 40 лет.
Проблема P=NP (или P≠NP) известна с 1971 года, но до сих пор считается неразрешенной. Разумеется, постоянно предпринимаются попытки решить эту задачу. Может, кто-то за миллионом гонится, а может ради науки.
Всего существует три возможных ответа на вопрос проблемы. 1) "P=NP", 2) "P≠NP", 3) невозможно доказать, "P=NP или P≠NP". Мне, конечно, видится, что есть еще четвёртый вариант, который состоит в том, что верен третий вариант, но невозможно доказать, что третий вариант верен, то есть что "P=NP?" доказать невозможно, но мы в эти дебри лезть не будем.
Австрийский математик Gerhard J. Woeginger создал в интернете страничку (https://www.win.tue.nl/~gwoegi/P-versus-NP.htm), куда собирает "доказательства" для проблемы P=NP в хронологическом порядке. Таких доказательств уже 107 штук и датированы они начиная с 1986 года по 2015.
Каждое "доказательство" имеет одну из трех пометок "Equal", "Not equal", "Unprovable", что соответствует трем описанным выше случаям. Четвертый случай по понятным причинам не мог бы возникнуть в этом списке. Кроме того, там написана краткая идея каждого из 107 доказательств.
Например, в марте 2014 года Joonmo Kim доказал, что P≠NP. Доказательство использует искусственно разработанную машину Тьюринга, которая генерирует экземпляры задачи выполнимости, и проверяет их выполнимость. А в сентябре 2014 года Анатолий Панюков доказал P = NP путем построения алгоритма решения задачи о Гамильтоновом пути в графе за полиномиальное время. В его статье так и указано прям, за
Так как все 107 доказательств не могут быть верны одновременно, то примерно половина из них гарантированно содержит ошибки: либо те, что утверждают, что P=NP, либо остальные. Ко многим доказательствам имеется ссылка на pdf-файл с научной статьей. Каждый желающий может поискать ошибки и, возможно, исправить.
Думаю, что скоро новые доказательства появятся. Миллион все еще ждет своего гения.
Сообщения
