Algorithmic analysis of parity games

Бесплатный доступ

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

Статья научная