We are trying to determine if the Simple Stochastic Game   (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 , 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.
 Anne Condon,
 Anne Condon, Information and Computation,
vol. 96, No. 2, February 1992, pp. 203-224.,
DIMACS Series in Discrete Mathematics and Theoretical Computer
Science, Volume 13, edited by Jin-Yi Cai, American Mathematical
Society, 1993, pp. 51-73.
 Manuel Blum, Rachel Rue, and Ke Yang, ,
Technical Report CMU-CS-02-110, Department of Computer Science,
Carnegie Mellon University, 2002.
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
Back to the REU page