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