Доклады Российской академии наук. Математика, информатика, процессы управления
RUS  ENG    ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ПАКЕТ AMSBIB  
Общая информация
Последний выпуск
Архив
Импакт-фактор

Поиск публикаций
Поиск ссылок

RSS
Последний выпуск
Текущие выпуски
Архивные выпуски
Что такое RSS


Докл. РАН. Матем., информ., проц. упр.:
Год:
Том:
Выпуск:
Страница:
Найти




Персональный вход:
Логин:
Пароль:
Запомнить пароль
Войти
Забыли пароль?
Регистрация

Доклады Российской академии наук. Математика, информатика, процессы управления, 2025, том 527, страницы 206–216
DOI: https://doi.org/10.7868/S2686954325070173 (Mi danma679) 		 
СПЕЦИАЛЬНЫЙ ВЫПУСК: ТЕХНОЛОГИИ ИСКУССТВЕННОГО ИНТЕЛЛЕКТА И МАШИННОГО ОБУЧЕНИЯ

NP-полнота игры “Ханаби” при минимальных параметрах

А. А. Оноприенко

Национальный исследовательский университет "Высшая школа экономики", Москва, Россия
DOI: https://doi.org/10.7868/S2686954325070173
Аннотация: Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и обмениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае дальнейшего уменьшения этих параметров игра оказывается разрешимой за полиномиальное время.
Ключевые слова: алгоритмическая теория игр, вычислительная сложность, NP-полнота, Ханаби.
Финансовая поддержка Номер гранта
Национальный исследовательский университет "Высшая школа экономики"
Статья подготовлена в ходе проведения исследования в рамках проекта “Международное академическое сотрудничество” НИУ ВШЭ.
Поступило: 12.08.2025
Принято к публикации: 22.09.2025
Реферативные базы данных:
Тип публикации: Статья
УДК: 004.8
Образец цитирования: А. А. Оноприенко, “NP-полнота игры “Ханаби” при минимальных параметрах”, Докл. РАН. Матем., информ., проц. упр., 527 (2025), 206–216
Цитирование в формате AMSBIB
\RBibitem{Ono25}
\by А.~А.~Оноприенко
\paper NP-полнота игры ``Ханаби'' при минимальных параметрах
\jour Докл. РАН. Матем., информ., проц. упр.
\yr 2025
\vol 527
\pages 206--216
\mathnet{http://mi.mathnet.ru/danma679}
\elib{https://elibrary.ru/item.asp?id=83189204}
Образцы ссылок на эту страницу:
  • https://www.mathnet.ru/rus/danma679
  • https://www.mathnet.ru/rus/danma/v527/p206
    • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    		Доклады Российской академии наук. Математика, информатика, процессы управления Доклады Российской академии наук. Математика, информатика, процессы управления
    Статистика просмотров:
    Страница аннотации:25
     
      Обратная связь:
    		  Пользовательское соглашение  Регистрация посетителей портала  Логотипы © Математический институт им. В. А. Стеклова РАН, 2026