Математик доказал сложность Candy Crush Saga
Профессор Тоби Уолш из университета Нового Южного Уэльса в Австралии доказал, что пазл Candy Crush Saga — разновидность математических NP-полных задач: чем больше конфет на игровом поле, тем сложнее найти решение. Метод исследования объяснил сайт New Scientist.
Чтобы подступиться к Candy Crush Saga, Уолш представил последовательность конфет в виде булевой формулы с логическими переменными и связками. Для такой формулы можно поставить задачу о выполнимости: есть ли такие значения переменных, что формула становится истинной. Эта задача — NP-трудная, а значит, Candy Crush Saga тоже такова.
На этом Уолш не остановился и выяснил, что Candy Crush Saga принадлежит к подклассу NP-полных задач. Чем больше переменных в таких задачах, тем сложнее их решить. Многие математики допускают, что NP-полные задачи — во всяком случае, некоторые из них — невозможно решить. Оттого Уолш рассудил, что было бы замечательно, если миллионы игроков в Candy Crush Saga подспудно помогли бы науке. Также он подчеркнул, что «NP-сложность» напрямую не связана со сложностью самой игры, но не исключил, что эти вещи как-то связаны.
Ранее математики из Массачусетского технологического института доказали, что Mario, Donkey Kong, The Legend of Zelda, Metroid и Pokemon относятся к классу NP-трудных задач.
Candy Crush Saga — пазл студии King. Вышел 12 апреля 2012 года в Facebook и 14 ноября на iOS и Android. В марте 2013 года она стала самой популярной игрой на Facebook (46 млн человек в месяц), обойдя FarmVille 2. Игра набрала на агрегаторе рецензий GameRankings средний балл 78% (iOS).
