Algorithmic analysis of parity games
Автор: Chernichkin M.S.
Журнал: Математическая физика и компьютерное моделирование @mpcm-jvolsu
Рубрика: Математика
Статья в выпуске: 8, 2004 года.
Бесплатный доступ
We consider an application of stationary balance searching algorithm in cyclic games [1] for solving parity games. Algorithm is presented with it's exponential complexity estimation, and we provide an example of parity game structure, for which this complexity is reached. Parity games are known to be in NP ∩ co-NP, and no polynomial algorithm is known for them.
Короткий адрес: https://sciup.org/14968552
IDR: 14968552
Статья научная