Email this article Exponential examples of solving parity games
- Authors: Lebedev V.N.1
-
Affiliations:
- Volgograd State University
- Issue: Vol 56, No 4 (2016)
- Pages: 688-697
- Section: Article
- URL: https://journal-vniispk.ru/0965-5425/article/view/178418
- DOI: https://doi.org/10.1134/S0965542516040114
- ID: 178418
Cite item
Open Access
Access granted
Subscription Access
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.
About the authors
V. N. Lebedev
Volgograd State University
Author for correspondence.
Email: lebedevvn@mail.ru
Russian Federation, Universitetskii pr. 100, Volgograd, 400062
Supplementary files
