REU: Simple Stochastic Game, ALADDIN Center

We are trying to determine if the Simple Stochastic Game [1] [2] (or Stable Circuit Problem) is PLS-complete. The originator of this problem, Anne Condon, does not know whether it is PLS-complete, nor is she aware of any work on the subject. The faculty advisor, Manuel Blum, has tried to put this problem—which is in NP intersect co-NP—into random polynomial time [3], but encountered great difficulty. Professor Blum discussed this problem with Christos Papadimitriou, the inventor of PLS-completeness, who thought that the question whether or not the Stable Circuit Problem is PLS-complete is truly interesting. Showing that the problem is PLS-complete would explain why so much difficulty was encountered in previous efforts to put the problem into random polynomial time.

[1] Anne Condon, The Complexity of Stochastic Games, Information and Computation, vol. 96, No. 2, February 1992, pp. 203-224.
[2] Anne Condon, On Algorithms for Simple Stochastic Games, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, Volume 13, edited by Jin-Yi Cai, American Mathematical Society, 1993, pp. 51-73.
[3] Manuel Blum, Rachel Rue, and Ke Yang, On the Complexity of MAX/MIN/AVRG Circuits, Technical Report CMU-CS-02-110, Department of Computer Science, Carnegie Mellon University, 2002.

Preliminary Presentation (ppt)
Final Presentation (ppt)

Other REUs for Summer 2004

Algorithms for Dynamic Point Location with Good Practical Performance
A Bezier-Based Approach to Unstructured Moving Meshes
Evaluation of Algorithms for the List Update Problem
Exploring PLS-Completeness of Simple Stochastic Game (or Stable Circuit Problem)
Fast and Compact Data Structures
The Game of NimG (Nim on Graphs)
Random Graph Models of Large Real-World Networks
Solving Partial Differential Equations Numerically
Traceable Anonymity

Back to the REU page