THE COMPLEXITY OF STOCHASTIC GAMES

被引：296
作者：
CONDON, A
机构：
[1] Computer Sciences Department, University of Wisconsin-Madison, Madison, WI 53706
来源：
INFORMATION AND COMPUTATION | 1992年 / 96卷 / 02期
关键词：
D O I：
10.1016/0890-5401(92)90048-K
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We consider the complexity of stochastic games-simple games of chance played by two players. We show that the problem of deciding which player has the greatest chance of winning the game is in the class NP {frown} co-NP. © 1992.
引用
收藏
页码：203 / 224
页数：22
相关论文
共 11 条
[1]  
[Anonymous], 1960, FINITE MARKOV CHAINS
[2]   ALTERNATION [J].
CHANDRA, AK ;
KOZEN, DC ;
STOCKMEYER, LJ .
JOURNAL OF THE ACM, 1981, 28 (01) :114-133
[3]  
Condon Anne, 1989, COMPUTATIONAL MODELS
[4]  
DERMAN C, 1972, FINITE STATE MARKOVI
[5]   ORDERED FIELD PROPERTY FOR STOCHASTIC GAMES WHEN THE PLAYER WHO CONTROLS TRANSITIONS CHANGES FROM STATE TO STATE [J].
FILAR, JA .
JOURNAL OF OPTIMIZATION THEORY AND APPLICATIONS, 1981, 34 (04) :503-515
[6]   COMPUTATIONAL COMPLEXITY OF PROBABILISTIC TURING MACHINES [J].
GILL, J .
SIAM JOURNAL ON COMPUTING, 1977, 6 (04) :675-695
[7]  
Howard RonaldA., 1960, DYNAMIC PROGRAMMING
[8]  
Khachian L. G., 1979, SOV MATH DOKL, V20, P191
[9]   GAMES AGAINST NATURE [J].
PAPADIMITRIOU, CH .
JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1985, 31 (02) :288-301
[10]  
Peters Hans J.M., 1987, CWI TRACT, V39
12