Задача о восьми ферзях, 1 миллион долларов и фейк

Начало сентября 2017 года ознаменовалось очередным фейком, связанным с математикой, который распространили средства массовой информации всего мира, в том числе и российские.

Информационное пространство взорвалось новостью в различных интерпретациях о том, что ​ученые из британского Сент-Эндрюсского университета якобы предложили $1 млн. за решение старинной шахматной задачи под названием «Задача о восьми ферзях». Даже проект Рамблера «Индикатор», претендующий на научность, опубликовал эту фейковую «новость».

На самом деле новость является фейковой, никакого миллиона долларов британские учёные никому не обещали. Что же произошло в действительности? Расскажем обо всём по-порядку, напомнив, что представляет собой задача о восьми ферзях.

Задача о восьми ферзях была сформулирована в середине XIX века. Необходимо найти способ расставить на шахматной доске восемь ферзей таким образом, чтобы ни один из них не попадал под удар любого другого. Решение для стандартной шахматной доски нашлось практически сразу после публикации задачи, но с увеличением размеров доски и количества фигур поиск решения существенно усложняется.

Трое учёных Сент-Эндрюсского университета опубликовали статью «Complexity of n-Queens Completion» в научном издании «Journal of Artificial Intelligence Research». После авторы статьи 31 августа 2017 года на официальном сайте своего университета публикуют статью под названием «Simple chess puzzle holds key to $1m prize» (рус. «Простая» шахматная задача содержит ключ к призу в 1 миллион долларов), посвящённую их научной статье. В тексте на сайте университета британцы лишь упоминают, что решение предложенной ими задачи может приблизить к получению приза в 1 млн. долларов, предлагаемого американским Математическим институтом Клэя, известным благодаря огромным денежным призам за решение «Задач тысячеления» (Millenium Prize Problems). При этом они используют английское выражение «conclude the rewards», интерпретация которого может быть достаточно широкой. Ни одного слова об обещании выплатить 1 млн. долларов кому-либо нет.

Поскольку фейк получил достаточно широкую огласку по всему миру, Математический институт Клэя был вынужден опубликовать опровержение в новостном разделе своего веб-сайта, где, в частности, указано: «Статья (британских учёных — авт.) представляет собой значительный вклад в развитие теории сложности вычислений, но в ней нет ни слова о том, что решение задачи о 8 ферзях или n ферзях эквивалентно получению приза за решение одной из задач тысячелетия. […] К сожалению, некоторые публикации формируют впечатление о том, что решение задачи о 8 ферзях или задачи о n ферзях для любого n, может привести к получению «Приза тысячелетия». Это не соответствует действительности по двум причинам. Во-первых, как было упомянуто, в статье речь идёт о полноте задачи о 8 ферзях, а не о самой задаче о 8 ферзях. Во-вторых, даже если будет найдено алгоритмическое решение проблемы полноты задачи о n ферзях для любого n, то этого будет недостаточно. После необходимо будет либо доказать, что либо алгоритм способен решить проблему полноты задачи о 8 ферзях за полиномиальное время, либо предоставить доказательство, что такого алгоритма не существует».

Чтобы досконально понять, о чём идёт речь в опровержении Математического института Клэя, следует вспомнить, что NP-полной задачей в теории алгоритмов называют задачу с ответом «да» или «нет» из класса NP, к которой можно свести любую другую задачу из этого класса за полиномиальное время. Кроме того, надо напомнить, что одной из «Задач тысячелетия», за решение которой институт Клэя выплатит 1 млн. долларов, является задача о равенстве классов P и NP, с которой «Задача о 8 ферзях» связана как частный случай.

Вернуться назад...

МЕТКИ >, ,