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