За "проста" наглед шахматна задача дават 1 млн долара

НаукаOFFNews Последна промяна на 02 септември 2017 в 12:54 39472 0

Кредит FlankerFF/Wikipedia Commons

Трима учени от шотландския университет Сейнт Андрюс хвърлиха ръкавицата към програмистите - награда от 1 милион долара на този, чиято програма може бързо да реши един привидно прост шахматен проблем, наречен "задачата за осемте царици".

Статията е публикувана в Journal of Artificial Intelligence Research.

Задачата за осемте царици е формулирана в средата на XIX век. Необходимо е да се намери начин да се поставят осем царици на шахматната дъска по такъв начин, че нито една от тях да не застрашава друга. Решението за стандартната шахматна дъска бе открито почти веднага след публикуването на задачата, но с увеличаването на размера на дъската и броя на фигурите търсенето на решение стана по-сложно, обяснява phys.org

Статията предупреждава, че да се докаже дали може да се реши бързо задачата за N царици за NxN дъска означава по същество да се докаже равенството или неравенството на класовете P и NP - една от "задачите на хилядолетието", за които Институтът Клей дава по 1 млн долара.

Проблемът на равенството P = NP се състои в следното: ако отговорът на някакъв въпрос може бързо да се провери (за полиномиално време), то вярно ли е, че отговорът на този въпрос може бързо да се намери (също за полиномиално време и използвайки полиномиална памет)?

Казано по-просто: задължително ли е по-лесно да се провери една задача, отколкото да се реши?

Полиномиално време за изпълнение означава, че времето за изпълнение на даден алгоритъм е полиномна функция на размера на входните данни, а не експоненциална. Например ако една програма изпълнява n-1 на брой сравнения в първия цикъл и n на брой сравнения във втория цикъл и така по отношение на сравненията нейното време за изпълнение е 2n-1, което е полином, следователно алгоритъмът работи в полиномно време. Има алгоритми, за които времето за изпълнение е друга функция на размера на входните данни (например 2n) и те не са полиномни, в случая - експоненциални.

Но задачата с увеличаване на броя на цариците става все по-сложна - за n = 27 и броят на решенията е повече от 2.34 * 10 17.

Авторите на статията установяват, че компютърните програми не могат да се справят с решаването на задачата, когато размерът на дъската стане 1000 х 1000 клетки, заради огромния брой варианти. Компютърните програми ще потънат в работа, подобно на измисления суперкомпютър от "Пътеводител на галактическия стопаджия " на Дъглас Адамс, който след седем и половина милиона години даде отговор на смисъла на живота (който не го знае, да прочете книгата).

Според един от авторите, професор Иън Гент (Ian Gent) от Университета Сейнт Андрюс, този, който може да се напише програма, способна да реши задачата бързо, може да я приспособи и за решаването и на други важни и трудни проблеми за сигурността в интернет.

"Наградата от 1 милион долара ще отидат за този, който може да докаже, че е възможно или не е възможно задачата да бъде решена бързо, така че наградата е достатъчно голяма" - добавя съавторът и колега на Гент, Кристофър Джеферсън (Christopher Jefferson).

Най-важното
Всички новини
За писането на коментар е необходима регистрация.
Моля, регистрирайте се от TУК!
Ако вече имате регистрация, натиснете ТУК!

Няма коментари към тази новина !