?
NP-полнота игры “Ханаби” при минимальных параметрах
Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика). 2025. № 527. С. 206–216.
Мы исследуем кооперативную карточную игру “Ханаби” с точки зрения алгоритмической сложности. Особенность “Ханаби” заключается в том, что игроки видят карты других игроков, но не свои, и об- мениваются информацией путем подсказок. Даже в модели с одним игроком, обладающим полной информацией о колоде, “Ханаби” остается NP-трудной. Найдены минимальные параметры игры, при которых сохраняется NP-трудность. В случае дальнейшего уменьшения этих параметров игра оказывается разрешимой за полиномиальное время.
Ключевые слова: вычислительная сложностьalgorithmic game theoryалгоритмическая теория игрNP-полнота NP-completenesscomputational complexityHanabiХанаби
ПУБЛИКАЦИЯ ПОДГОТОВЛЕНА ПО РЕЗУЛЬТАТАМ ПРОЕКТА:
Смирнов С. В., Миллионщиков Д. В., Уфимский математический журнал 2021 Т. 13 № 2 С. 44–73
В данной работе изучаются характеристические алгебры для систем экспоненциального типа, соответствующих вырожденным матрицам Картана. Эти системы обобщают хорошо известные в теории интегрируемых систем гиперболические уравнения синус-Гордон и Цицейки. Для таких систем, соответствующих матрицам Картана ранга 2, характеристические алгебры описаны явно в терминах образующих и соотношений, и доказано, что они имеют линейный рост. Исследуется связь между ...
Добавлено: 11 сентября 2026 г.
Смирнов С. В., Glasgow Mathematical Journal 2026 Vol. 68 No. 2 P. 299–316
Добавлено: 11 сентября 2026 г.
Смирнов С. В., Journal of Physics A: Mathematical and Theoretical 2023 Vol. 56 No. 26 Article 265204
Добавлено: 11 сентября 2026 г.
Энатская Н. Ю., Труды Карельского научного центра РАН. Серия 10: Математическое моделирование и информационные технологии 2026 № 6 С. 132–138
В схемах S размещения r частиц по n различимым ячейкам изучаются их размещения в выделенных m ячейках – схем S∗, для которых проводится анализ новым перечислительным методом (ПМ) по расширенным направлениям перечислительной комбинаторики: нахождения числа исходов и на основе построения модели их бесповторного нумерованного перечисления – решения для них задачи нумерации в прямой и обратной ...
Добавлено: 11 сентября 2026 г.
Энатская Н. Ю., Труды Карельского научного центра РАН. Серия 10: Математическое моделирование и информационные технологии 2026 № 6 С. 139–147
Рассматриваемый класс схем размещения частиц по ячейкам характеризуется введением верхнего ограничения уровней заполнения ячеек с его обязательным достижением хотя бы в одной ячейке каждого исхода каждой схемы. Схемы различаются между собой парными качествами составляющих их элементов (ячеек и частиц) по их различимостям. Из направлений исследования схем выделяются представляющие наибольший интерес по нестандартным приемам доасимптотического анализа ...
Добавлено: 11 сентября 2026 г.
Подиновский В. В., Нелюбин А. П., Автоматика и телемеханика 2026 № 8 С. 110–123
Для многокритериальных задач принятия решений по аналогии с качественной вероятностью введены понятия полной и частичной качественной важности как бинарных отношений, обладающих постулируемыми
свойствами. Предложено новое определение отношения нестрогого предпочтения на множестве вариантов решений, порождаемое качественной
важностью. Исследованы его свойства. Указаны аналитические правила,
позволяющие попарно сравнивать варианты по предпочтительности. Проведено сравнение новых отношений предпочтения с разработанными ранее для задач, ...
Добавлено: 9 сентября 2026 г.
Подиновский В. В., Нелюбин А. П., Автоматика и телемеханика 2026 № 7 С. 113–126
Рассматриваются задачи принятия решений, когда предпочтения оцениваются в порядковой шкале, а возможности реализации значений
неопределенного фактора описываются качественной вероятностью (полной или только частичной). Вводятся определения отношений предпочтения и безразличий на множестве стратегий. Предлагаются простые
решающие правила, позволяющие сравнивать стратегии по предпочтительности, и приводятся иллюстративные примеры. ...
Добавлено: 9 сентября 2026 г.
Chemical Papers 2026
Добавлено: 8 сентября 2026 г.
Александров А. А., Глуцюк А. А., Journal of Differential Equations 2026 Vol. 465 Article 114178
Добавлено: 8 сентября 2026 г.
Prikhodko Artem, Kubrak D., Compositio Mathematica 2026 Vol. 162 No. 6 P. 1377–1438
Добавлено: 7 сентября 2026 г.
Кучерявый П. А., Математические заметки 2026 Т. 2026 № 120 С. 380–401
В работе изучаются перестановки, возникающие при упорядочивании по возрастанию дробных долей произведений элементов фиксированной целочисленной последовательности на вещественный параметр. Исследуется количество различных перестановок, которые можно получить таким образом при изменении этого параметра от нуля до единицы. ...
Добавлено: 7 сентября 2026 г.
Осипов Д.В., Математический сборник 2026 Т. 217 № 9 С. 130–146
Изучаются законы взаимности, связанные с комплексными линейными расслоениями на расслоениях на ориентируемые окружности. В частности, доказывается следующий закон взаимности. Пусть B – комплексное многообразие и πi:Mi→B – расслоение на ориентируемые окружности, где индекс i пробегает конечное множество. Пусть Li и Ni – комплексные линейные расслоения на каждом многообразии Mi. Закон взаимности утверждает, что сумма всех элементов (πi)∗(c1(Li)∪c1(Ni)), где (πi)∗ – ...
Добавлено: 3 сентября 2026 г.
Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2026 Vol. 36 No. 6 Article exag026
Добавлено: 1 сентября 2026 г.
Добавлено: 28 мая 2026 г.
Дудаков С. М., Карлов Б. Н., Доклады Российской академии наук. Математика, информатика, процессы управления (ранее - Доклады Академии Наук. Математика) 2025 Т. 524 № 1 С. 11–18
В работе изучается проблема тотальной выводимости в контекстно-свободных, неукорачивающих и контекстно-зависимых грамматиках. Для фиксированного терминального слова проблема состоит в том, чтобы по грамматике определить, существует ли вывод этого слова, в котором каждое правило используется не менее некоторого заданного числа раз. Доказывается, что проблема тотальной выводимости пустого слова в контекстно-свободной грамматике является NP-полной. Для неукорачивающих и ...
Добавлено: 18 марта 2026 г.
Иванашев Я. М., , in: 19th Annual Conference, TAMC 2025, Jinan, China, September 19–21, 2025, Proceedings. Theory and Applications of Models of Computation. Lecture Notes in Computer Science (LNCS, volume 16084)Vol. 16084.: Springer, 2026. P. 15–24.
Добавлено: 20 января 2026 г.
Odintsov S., Сперанский С. О., Logic and Logical Philosophy 2012 Vol. 21 No. 3 P. 209–228
The present paper is devoted to computational aspects of propositional inconsistency-adaptive logics. In particular, we prove (relativized versions of) some principal results on computational complexity of derivability in such logics, namely in cases of CLuN-r and CLuN-m , i.e., CLuN supplied with the reliability strategy and the minimal abnormality strategy, respectively. ...
Добавлено: 27 декабря 2025 г.
Сперанский С. О., Studia Logica 2013 Vol. 101 No. 6 P. 1237–1262
In a rather general setting, we prove a number of basic theorems concerning computational complexity of derivability in adaptive logics. For that setting, the so-called standard format of adaptive logics is suitably adopted, and the corresponding completeness results are established in a very uniform way. ...
Добавлено: 27 декабря 2025 г.