16.09.2012

Ставка - миллион долларов

Она входит в семерку задача миллениума, которые остаются нерешенными многие годы. За доказательство каждой Институтом Клэя учрежден приз в миллион долларов. До сих пор решена только одна из этих сложнейших задач - гипотеза Пуанкаре. Ее "расколол" российский математик Григорий Перельман, отказавшийся от миллиона долларов.

Сейчас речь о задаче P vs NP. Она формулируется так: если положительный ответ на какой-то вопрос можно быстро проверить, то правда ли, что ответ на этот вопрос можно быстро найти. Иначе говоря, действительно ли решение задачи легче проверить, нежели отыскать. Математики не раз атаковали эту задачу. Последний штурм был предпринят в 2010 году американским профессором Деолаликаром, однако в формулах были обнаружены ошибки. Та же судьба постигла несколько лет назад и доказательство украинского профессора из Луганска Александра Плотникова. Ему указали на частный характер решения. И вот новая попытка украинца. Свое доказательство Плотников опубликовал в международном научном журнале Journal of computer science. Сам факт такой публикации дает ученому неплохие шансы на успех. Ведь каждая статья дотошно рецензируется независимыми экспертами мирового уровня.

Доказательство задачи P vs NP имеет важное практическое значение. В частности, оно может помочь совершить прорывы в криптологии за счет создания принципиально новых методов защиты информации с ограниченным доступом (банковской, военной, коммерческой тайн). Сейчас вариант решения, предложенный Плотниковым, проходит дальнейшую проверку.

Юрий Медведев

Источники:

1. Российская газета