Работники минской IT-компании Дмитрий Литвинович и Евгений Клещук прочитали о награде в миллион долларов за решение шахматной задачи — и создали программу, которая превосходит многие существующие. Правда, позже оказалось, что миллион платят не за само решение, а за ответ на более сложный вопрос.
Миллион за «быстрое» решение
Новость про «Задачу о ферзях» облетела СМИ в сентябре 2017 года. На TUT.BY она появилась под заголовком «Британские ученые пообещали миллион долларов за разгадку шахматной задачи». Речь в ней шла об ученых из Сент-Эндрюсского университета в Великобритании, которые изучали шахматную задачу и рассуждали о перспективах ее решения.
Суть задачи заключается в том, чтобы расставить на шахматной доске восемь ферзей таким образом, чтобы ни один из них не попадал под удар другого. Подразумевается, что ферзь бьет все клетки, расположенные на одной с ним вертикали, горизонтали или диагонали.
Для восьми ферзей и доски 8 на 8 клеток решить задачу легко. А вот с увеличением размеров поля и количества фигур задача усложняется. Британские исследователи обнаружили, что если размер доски увеличить до 1000 на 1000 клеток, компьютерные программы начинают зависать. Также они отметили, что создатель программы, которая докажет, есть ли у задачи «быстрое» решение, может рассчитывать на приз в миллион долларов. Сами они уверены, что такая программа невозможна.
«Не совсем перебор»
Сотрудники одной минской IT-компании OnePoint Дмитрий Литвинович и Евгений Клещук решили попробовать. За полгода работы они создали алгоритм, который рассчитывает решение для доски с заданным размером. Программа работает на обычных компьютерах и мобильных телефонах. С задачей для 1000 ферзей она справляется за три минуты.
— Это не совсем перебор, там есть определенный алгоритм, — рассказал Дмитрий. — От обычного перебора, пишут, зависает компьютер. Здесь есть конкретная логика, по которой высчитывается позиция каждой конкретной фигуры, а не просто перечисляются варианты.
Молодые люди обратились в институт за вознаграждением, но выяснилось, что деньги обещали не совсем за это. Выплатой миллиона долларов занимается не британский Сент-Эндрюсский университет, а американский институт Клэя. Он готов заплатить любому, кто докажет, равны ли математические классы P и NP.
Шахматная задача о ферзях может лишь помочь в поиске ответа на вопрос о P и NP. Правда, из-за того, что британский институт выпустил сообщение с заголовком «шахматная головоломка содержит ключ к призу в миллион долларов» получилась путаница, а по интернету разлетелась новость, которую все поняли не так.
— Я не совсем расстроился, — рассказывает Дмитрий. — Если они так написали, это, возможно, все-таки является ключом. Может, стоит как-то шире поработать над этой программой или связаться с тем профессором, который эту мысль озвучил.
Переключаться на математическую «задачу тысячелетия» Дмитрий пока не планирует.
— Я не великий математик, я немного другим себе на хлеб зарабатываю. Но если вдруг у меня появится знакомый математик, который подскажет, как это можно воплотить, — то, может быть, займусь. Пока я буду работать с тем, что есть.
Что за задача об P и NP?
Классом P называют множество задач, которые компьютер может решить «быстро» (то есть за полиномиальное время). К ним относят базовые арифметические действия, сортировку списков, поиск по таблице с данными.
Класс NP — это задачи, правильность ответа на которые можно быстро проверить. Например, задача о сумме. Предположим, что у вас есть монеты номиналом 2, 3, 5, 6 и 7 рублей, по одной каждого номинала, и вы хотите без сдачи оплатить покупку стоимостью 21 рубль. Можно ли набрать из данных монет сумму, равную 21?
В этой задаче для получения ответа нужно перебрать разные варианты, а чтобы доказать, что решения нет, — вообще перебрать все возможные варианты. Если количество монет увеличить на несколько порядков, решение выглядит совсем непрактичным. При этом результат проверить легко — просто сложить номиналы всех монет.
Суть «задачи тысячелетия» формулируется так: равны ли классы P и NP? Если легко проверить правильность решения задачи, может ли быть так же легко решить эту задачу? Большинство специалистов уверены, что ответ отрицательный. Однако доказать этого пока никто не смог. Если же вдруг окажется, что P = NP, то человечество ждет переворот в криптографии. Именно за это решение американский институт Клэя готов заплатить миллион долларов.