The complexity of stochastic games
作者： Anne Condon
DOI: 10.1016/0890-5401(92)90048-K
关键词: Artificial intelligence 、 Combinatorial game theory 、 Mathematical economics 、 Game of chance 、 Mathematics 、 Turing machine 、 Parity game 、 Class (computer programming) 、 Directed graph 、 PPAD 、 Stochastic game
摘要: Abstract We consider the complexity of stochastic games—simple games chance played by two players. show that problem deciding which player has greatest winning game is in class NP ⌢ co- .
acm.org
elsevier.com
sci-hub.se 参考文章(7)
Anne Elizabeth Condon, Computational Models of Games ,(1989)
Christos H. Papadimitriou, Games against nature Journal of Computer and System Sciences. ,vol. 31, pp. 288- 301 ,(1985) , 10.1016/0022-0000(85)90045-5
Ronald A. Howard, Dynamic Programming and Markov Processes ,(1960)
L.G. Khachiyan, Polynomial algorithms in linear programming USSR Computational Mathematics and Mathematical Physics. ,vol. 20, pp. 53- 72 ,(1980) , 10.1016/0041-5553(80)90061-0
J. A. Filar, Ordered field property for stochastic games when the player who controls transitions changes from state to state Journal of Optimization Theory and Applications. ,vol. 34, pp. 503- 515 ,(1981) , 10.1007/BF00935890
John Gill, Computational Complexity of Probabilistic Turing Machines SIAM Journal on Computing. ,vol. 6, pp. 675- 695 ,(1977) , 10.1137/0206049
L. S. Shapley, Stochastic Games Proceedings of the National Academy of Sciences of the United States of America. ,vol. 39, pp. 1095- 1100 ,(1953) , 10.1073/PNAS.39.10.1095