Ученые из Сент-Эндрюсского университета выяснили, что если в шахматной головоломке под названием «Задача о восьми ферзях» увеличить площадь доски во много раз, то программа не сможет ее решить. Любой, кто придумает алгоритм для решения, после этого сможет решить одну из «задач тысячелетия». Об этом написали 31 августа на сайте университета.
По условиям задачи, известной с 1850 года, необходимо расставить на 64-клеточной шахматной доске восемь ферзей так, чтобы ни один из них не атаковал другого. У задачи несколько решений и с ней может справиться и компьютер, и человек. Но при увеличении размера шахматной доски (до 1000х1000 клеток) современные компьютеры не могут справиться с огромным количеством вариантов решения задачи и зависают.
По словам одного из ученых университета, Иэна Гента, если кому-то удастся написать программу, которая решит «Задачу о восьми ферзях» быстро, то ее можно будет потом использовать для решения множества других проблем. По словам ученого, речь идет о, например, написании алгоритма, который сможет вычислить самую большую группу друзей пользователя фейсбука, которые не знаю друг друга. Или позволит взломать код, который хранит данные обо всех онлайн-транзакциях. Сами специалисты считают, что написать такую программу невозможно.
Если кто-то сможет написать алгоритм, который позволит быстро решить эту задачу, то этот человек сможет решить вопрос о равенстве классов сложности P и NP. Еще он известен как «проблема перебора». За ее решение математический институт Клэя в США выплатит один миллион долларов.
Проблема равенства классов P и NP — это одна из семи задач тысячелетия. Среди других задач: гипотеза Ходжа, гипотеза Пуанкаре и теория Янга — Миллса. За решение каждой из этих задач институт Клэя выплатит миллион долларов.
С 2000 года удалось решить только одну задачу тысячелетия. В 2006 году российский математик Григорий Перельман доказал исходную гипотезу Пуанкаре. За это его удостоили Филдсовской премии, но ученый отказался ее принять.