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.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
V. A. Gurvich, A. V. Karzanov, and L. G. Khachiyan, “Cyclic games and an algorithm to find minimax cycle means in directed graphs,” Zh. Vychisl. Mat. Mat. Fiz. 28 (5), 85–91 1988.
N. Pisaruk, “Mean cost cyclical games,” Math. Oper. Res. 59 (4), 817–828 1999.
A. V. Karzanov and V. N. Lebedev, “Cyclical games with prohibitions,” Math. Program. 60, 277–293 1993.
M. Jurdzinski, “Deciding the winner in parity games is in UP n co–UP,” Inf. Proc. Lett. 68, 119–124 1998.
E. Beffara and S. Vorobyov, “Is randomized Gurvich–Karzanov–Khachiyan’s algorithm for parity games polynomial?” Technical report, Department of information Technology Uppsala University, 2001.
Author information
Authors and Affiliations
Corresponding author
Additional information
Original Russian Text © V.N. Lebedev, 2016, published in Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 2016, Vol. 56, No. 4, pp. 694–703.
Rights and permissions
About this article
Cite this article
Lebedev, V.N. Exponential examples of solving parity games. Comput. Math. and Math. Phys. 56, 688–697 (2016). https://doi.org/10.1134/S0965542516040114
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1134/S0965542516040114