Abstract:
This paper is devoted to solving certain problems on the computational complexity of deciding the winner in cyclic games. The main result is the proof of the fact that the nondeterministic potential transformation algorithm designed for solving parity games is exponential in terms of computation time.
Key words:cyclic game, potential transformations, computational complexity, deciding the winner in cyclic games.
Fulltext:
PDF file (203 kB)