EGuaranteeNash for Boolean Games Is NEXP-Hard

Публикации

?

EGuaranteeNash for Boolean Games Is NEXP-Hard

Яновский Е. А., Ong L.

Язык: английский

Текст на другом сайте

В книге

Proceedings, Fourteenth International Conference on Principles of Knowledge Representation and Reasoning (KR-14)

Palo Alto: AAAI Press, 2014.

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

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

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

Добавлено: 23 ноября 2025 г.

How to Guide a Present-Biased Agent Through Prescribed Tasks?

Belova T., Dementiev Y., Fomin F. и др., , in: 27th European Conference on Artificial Intelligence, 19–24 October 2024, Santiago de Compostela, Spain – Including 13th Conference on Prestigious Applications of Intelligent Systems (PAIS 2024)Vol. 392.: IOS Press, 2024. P. 3461–3468.

Добавлено: 24 октября 2024 г.

On efficient algorithms for bottleneck path problems with many sources

Kirill V. Kaymakov, Dmitry S. Malyshev, Optimization Letters 2024 Vol. 18 P. 1273–1283

Добавлено: 18 апреля 2024 г.

A complete complexity dichotomy of the edge-coloring problem for all sets of 8-edge forbidden subgraphs

Малышев Д. С., Duginov O. I., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 4 P. 791–801

Добавлено: 16 февраля 2024 г.

Comparative Analysis of Logic Reasoning and Graph Neural Networks for Ontology-Mediated Query Answering with a Covering Axiom

Герасимова О. А., Макаров И. А., Severin N., IEEE Access 2023 Vol. 11 P. 88074–88086

The problem of query answering over incomplete attributed graph data is a challenging field of database management systems and artificial intelligence. When there are rules on data structure expressed in the form of the ontology, the theoretical complexity of finding exact solution satisfying ontology constraints increases. Logic-based methods use theoretical constructions to obtain efficient rewritings ...

Добавлено: 5 января 2024 г.

The discrete Fourier transform over the binary finite field

Sergei Valentinovich Fedorenko, IEEE Access 2023 Vol. 11 P. 62771–62779

Добавлено: 19 июля 2023 г.

Inconsistent Planning: When in Doubt, Toss a Coin!

Dementiev Yuriy, Fomin F., Игнатьев А. А., , in: Thirty-Sixth AAAI Conference on Artificial IntelligenceVol. 36. Issue 9: AAAI-22 Technical Tracks 9.: Palo Alto: AAAI Press, 2022. P. 9724–9731.

Добавлено: 26 января 2023 г.

Thirty-Sixth AAAI Conference on Artificial Intelligence

Palo Alto: AAAI Press, 2022.

Добавлено: 26 января 2023 г.

Complexity function and complexity of validity of modal and superintuitionistic propositional logics

Рыбаков М. Н., Shkatov D., Journal of Logic and Computation 2023 Vol. 33 No. 7 P. 1566–1595

Добавлено: 6 января 2023 г.

Some cases of polynomial solvability of the edge coloring problem that are generated by forbidden 8-edge subcubic forests

Добавлено: 31 декабря 2022 г.

On a Countable Family of Boundary Graph Classes for the Dominating Set Problem

G. S. Dakhno, D. S. Malyshev, Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2023 Vol. 17 No. 1 P. 25–31

Наследственный класс — множество обыкновенных графов, замкнутое относительно удаления вершин, каждый такой класс задается множеством своих минимальных запрещенных порожденных подграфов. Если это множество конечно, то он называется конечно определенным. Понятие граничного класса является полезным инструментом анализа вычислительной сложности задач на графах в семействе конечно определенных классов. Задача о доминирующем множестве для заданного графа состоит в ...

Добавлено: 6 декабря 2022 г.

Comparing the Computational Complexity of Monomials and Elements of Finite Abelian Groups

Кочергин В. В., Moscow University Mathematics Bulletin 2022 Vol. 77 No. 3 P. 113–119

Добавлено: 29 октября 2022 г.

Complexity of finite-variable fragments of propositional temporal and modal logics of computation

Рыбаков М. Н., Shkatov D., Theoretical Computer Science 2022 Vol. 925 P. 45–60

Добавлено: 12 мая 2022 г.

An intractability result for the vertex 3-colourability problem

Malyshev D. S., Приставченко О. В., Optimization Letters 2022 Vol. 16 P. 1403–1409

Добавлено: 25 февраля 2022 г.

On computational complexity of set automata

Рубцов А. А., Вялый М. Н., Information and Computation 2021 Vol. 281 Article 104797

Добавлено: 2 февраля 2022 г.

Proceedings of the 17th International Conference on Principles of Knowledge Representation and Reasoning

Захарьящев М. В., Kontchakov R., Ryzhikov V. и др., The International Joint Conference on Artificial Intelligence (IJCAI), 2020.

Добавлено: 6 ноября 2021 г.

No-Rainbow Problem and the Surjective Constraint Satisfaction Problem

Жук Д. Н., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–7.

Добавлено: 8 сентября 2021 г.

Minimal Taylor Algebras as a Common Framework for the Three Algebraic Approaches to the CSP

Barto L., Brady Z., Bulatov M. и др., , in: 2021 36th Annual ACM/IEEE Symposium on Logic in Computer Science (LICS).: [б.и.], 2021. P. 1–13.

Добавлено: 8 сентября 2021 г.

On 3-colouring of graphs with short faces and bounded maximum vertex degree

Сироткин Д. В., Малышев Д. С., Lobachevskii Journal of Mathematics 2021 Vol. 42 No. 4 P. 760–766

Добавлено: 5 июня 2021 г.

Efficient solvability of the weighted vertex coloring problem for some two hereditary graph classes

Развенская О. О., Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2021 Vol. 15 No. 1 P. 97–117

Добавлено: 23 апреля 2021 г.

Efficient Algorithm for Finding Roots of Error-Locator Polynomials

Sergei Valentinovich Fedorenko, IEEE Access 2021 Vol. 9 P. 38673–38686

Добавлено: 15 апреля 2021 г.

Complete complexity dichotomy for 7-edge forbidden subgraphs in the edge coloring problem

Малышев Д. С., Journal of Applied and Industrial Mathematics (перевод журналов "Сибирский журнал индустриальной математики" и "Дискретный анализ и исследование операций") 2020 Vol. 14 No. 4 P. 706–721

Добавлено: 30 января 2021 г.

The vertex colourability problem for {claw,butterfly}-free graphs is polynomial-time solvable

Малышев Д. С., Optimization Letters 2021 Vol. 15 No. 2 P. 311–326

Добавлено: 6 января 2021 г.

Low-rank matrix approximation in the infinity norm

Gillis N., Шитов Я. Н., Linear Algebra and its Applications 2019 Vol. 581 P. 367–382

Добавлено: 11 ноября 2020 г.