Речь идёт про «Задачу о ферзях»: на шахматной доске необходимо расставить восемь ферзей так, чтобы они находились в безопасности от атак друг друга. Учёные из Великобритании выяснили, что при увеличении доски до 1000 клеток по одной стороне программы для вычисления задачи начинают зависать. Они отметили, что создатель работающей программы получит шанс заполучить $1 млн и сами считали такое развитие событий невозможным.

Дмитрий Литвинович и Евгений Клещук потратили полгода для создания алгоритма, который решает задачу для такой доски за три минуты и работает на обычных смартфонах и ПК.

«Это не совсем перебор, там есть опредёленный алгоритм. От обычного перебора, пишут, зависает компьютер. Здесь есть конкретная логика, по которой высчитывается позиция каждой конкретной фигуры, а не просто перечисляются варианты», — рассказал Дмитрий.

Когда программисты обратились в британский Сент-Эндрюсский университет за вознаграждением, выяснилось, что за выплату отвечает американский институт Клэя. Он готов заплатить деньги, но тому, кто докажет равенство математических классов P и NP. А «Задача про ферзей» должна помочь в поиске правильного решения. Путаница возникла из-за того, что около года назад британцы опубликовали статью с заголовком «Шахматная головоломка содержит ключ к призу в миллион долларов», которую подхватили различные издания.

«Я не совсем расстроился. Если они так написали, это, возможно, всё-таки является ключом. [...] Если вдруг у меня появится знакомый математик, который подскажет, как это можно воплотить, — то, может быть, займусь. Пока я буду работать с тем, что есть», — рассказывает Дмитрий.

В чём суть задачи про равенство P и NP?

Классом P называют множество задач, которые компьютер может решить «быстро» (то есть за полиномиальное время). К ним относят базовые арифметические действия, сортировку списков, поиск по таблице с данными. Класс NP — это задачи, правильность ответа на которые можно быстро проверить. Например, задача о сумме.

«Задача тысячелетия» должна доказать, что, если легко проверить правильность решения задачи, может ли быть так же легко решить эту задачу? Большинство математиков склоняются к тому, что ответ на этот вопрос отрицательный, но доказать это пока никто не смог. Доказательство равенства P и NP совершит переворот в криптографии, именно поэтому за решение задачи и готовы заплатить $1 млн.