Летом 2017–го года группа британских математиков из университета Сент Эндрюс доказала, что задача о расстановке n ферзей на доске n*n является NP–полной.

Летом 2017–го года группа британских математиков из университета Сент Эндрюс доказала, что задача о расстановке n ферзей на доске n*n является NP–полной.

Грубо говоря, это значит, что известные алгоритмы для решения задачи имеют экспоненциальную сложность, и если вдруг кто–то придумает более эффективный алгоритм, это автоматически даст нам более эффективные алгоритмы для широкого круга переборных задач.

Далее произошла череда недопониманий, которая часто возникает между журналистами, пишущими на научные темы, и учёными.

Напомню, что классическая головоломка о расстановке ферзей на шахматной доске звучит так: расставьте на шахматной доске восемь ферзей, чтобы они не били друг друга. То есть, чтобы на каждой горизонтали, вертикали и диагонали находилось не более одного ферзя. Очевидным образом, головоломка обощается на доску n*n клеток и n ферзей.

Сначала на сайте университета появилась заметка, где говорилось, что задача о расстановке ферзей на шахматной доске очень важна и сложна. И того, кто придумает алгоритм, быстро решающий задачу для доски порядка 1000*1000 клеток, ждёт приз в миллион долларов.

Вскоре эта новость разошлась по многим СМИ под заголовками: "Британские учёные пообещали миллион долларов за решение шахматной задачи"

Двое беларуских программистов создали алгоритм, находящий необходимую расстановку ферзей на доске 1000*1000 за три минуты (я так полагаю, на обычном персональном компьютере). Они связались с математиками из университета Сент Энрдрюс, и тут выяснилось, что:

Во–первых, миллион долларов обещали не они, а Институт Клэя.

Во–вторых, не за быстрое решение задачи о расстановке ферзей, а за ответ на вопрос, равны ли классы задач P и NP?

В первый класс входят задачи, которые можно решить за полиномиальное время (то есть, довольно быстро).

Во второй класс входят задачи, для которых за полиномиальное время можно проверить правильность ответа.

В–третьих, британские математики имели в виду не классическую головоломку о расстановке ферзей на доске, а задачу следующего вида: пусть на доске n*n стоит некоторое число ферзей, не бьющих друг друга. Можно ли к ним добавить ещё ферзей, чтобы на доске их стало n штук, и они всё равно не били друг друга? Вот если найти алгоритм, который за полиномиальное время сможет ответить на поставленный вопрос для любой начальной расстановки ферзей, а не только для пустой доски, это будет означать, что классы P и NP совпадают, за что Институт Клэя даст миллион.

В общем, остались ребята без награды.

Напоследок, предлагаю задачу: предложите способ расстановки тысячи ферзей на доске 1000*1000 так, чтобы они не били друг друга. Подсказка: для решения задачи компьютер не обязателен.

Комментарии: