Алгоритмический анализ игр на четность
Автор: Черничкин М.С.
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Математика
Статья в выпуске: 8, 2004 года.
Бесплатный доступ
Мы рассматриваем применение алгоритма поиска стационарных равновесий в циклических играх [1] для решения игр на четность. Представлен алгоритм, показана его экспоненциальная сложность и приведен пример, на котором эта оценка достигается. Известно, что игры на четность лежат в NP ∩ co-NP, и неизвестно ни одного полиномиального алгоритма для их решения.
Короткий адрес: https://sciup.org/14968552
IDR: 14968552
Список литературы Алгоритмический анализ игр на четность
- Лебедев В.Н. Поиск и структура стационарных равновесий в циклических играх//Математические заметки. 2000. Т. 67. № 6. С. 913-921.
- Emerson E.A., Jutla C.S., Sistla A.P. On model-checking for fragments of μ-calculus. In Computer Aided Verification: Proc. 5th Int. Workshop. Elounda, Crete, June 1993. Lecture Notes in Computer Science, Springer-Verlag.V. 697. P. 385-396.
Статья научная
