Вышла статья Анастасии Оноприенко «NP-полнота игры “Ханаби” при минимальных параметрах»

В журнале «Доклады Российской академии наук. Математика, информатика, процессы управления» опубликована статья Анастансии Оноприенко «NP-полнота игры “Ханаби” при минимальных параметрах».

Аннотация
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае дальнейшего уменьшения этих параметров игра оказывается разрешимой за полиномиальное время.

Оноприенко А.А. NP-полнота игры “Ханаби” при минимальных параметрах // Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2025. № 527. С. 206–216.