The Complexity of Simple Stochastic Games

2007/04/20 by Jonas Dieckelmann, Dieckelmann, Jonas
Computer Science · #Computational Complexity (cs.CC) #Computer Science and Game Theory (cs.GT) #FOS: Computer and information sciences #cs.CC #cs.GT

paper · pdf · doi:10.48550/arxiv.0704.2779

Hi, while reading through literature i noticed that it has not yet been proved that computing the value vector of simple stochastic games is a Problem in FNP. This is why i came up with a prove in this seminar work of mine

arxiv created 2007/04/20 · arxiv updated 2009/12/01

Abstract

In this paper we survey the computational time complexity of assorted simple stochastic game problems, and we give an overview of the best known algorithms associated with each problem.

Related

• Simple Recursive Games
• On the computational complexity of solving stochastic mean-payoff games
• Simple Stochastic Games, Parity Games, Mean Payoff Games and Discounted Payoff Games are all LP-Type Problems
• Solving simple stochastic games with few coin toss positions
• Simple Stochastic Stopping Games: A Generator and Benchmark Library