Symmetric Turing machine

Definition of symmetric Turing machines:

SL was first defined in 1982 by Lewis and Papadimitriou, [Jesper Jansson. [http://www.df.lth.se/~jj/Publications/STCON2.ps Deterministic Space-Bounded Graph Connectivity Algorithms] . Manuscript. 1998.] [Harry R. Lewis and Christos H. Papadimitriou. Symmetric space-bounded computation. "Theoretical Computer Science". pp.161-187. 1982.] who were looking for a class in which to place USTCON, which until this time could, at best, be placed only in NL,despite seeming not to require nondeterminism. They defined the symmetric Turing machine, used it to define SL. Symmetric Turing machines are kind of Turing machines with limited nondeterministic power. Informally Symmetric computations are reversible in an approximate manner. A symmetric computation is divided into locally deterministic sub computation ( segments ) between special configuration , where nondeterminism takes place , such that the only special configuration reached from a backward computation is the special configuration started the segment. Thus the segments are locally deterministic in its forward direction and have limited nondeterminism in its backward direction . Also if there is a way from special configuration A1 to special configuration A2 , there must be a way back from A2 to A1.

[http://moustafaemara.wordpress.com/files/2008/07/smturing.pngExample of Symmetric Configuration]

Symmetric log space complexity:

* SSPACE(S(n) is the class of the languages accepted by a symmetric Turing machine running in space O(S(n))
* SL is The class of problems solvable by a nondeterministic Turing machine in logarithmic space, such that
*# If the answer is 'yes,' one or more computation paths accept.
*# If the answer is 'no,' all paths reject.
*# If the machine can make a nondeterministic transition from configuration A to configuration B, then it can also transition from B to A. (This is what 'symmetric' means.)
*# It was proved That SL = Co­SL

Idea about why USTCON is SL-complete

The most important Complete Problem is the USTCON , Lewis and Papadimitriou by their definition showed that USTCON is complete for SL class. They constructed a nondeterministic machine for USTCON , and they made a lemma for converting this machine into Symmetric Turing Machine. Then the theorem follows as any language can be accepted using a symmetric Turing machine is log­space reducible to USTCON as from the properties of the symmetric computation we can view the special configuration as the undirected edges of the graph.

References

[ O. Reingold, Undirected ST­Connectivity in Log­Space, STOC 2005. ] Reingold, Undirected ST­Connectivity in Log­Space, STOC 2005. [ 1. Lecture Notes :CS369E: Expanders in Computer Science By Cynthia Dwork & Prahladh Harsha ] Lecture Notes :CS369E: Expanders in Computer Science By Cynthia Dwork & Prahladh Harsha [ 2. http://www.cs.huji.ac.il/~advtheory Lecture Notes] http://www.cs.huji.ac.il/~advtheory Lecture Notes [ 3. Symmetric LogSpace is closed undercomplement Noam Nissa] Symmetric LogSpace is closed undercomplement Noam Nissa [ 4. Sharon Bruckner Lecture Notes] Sharon Bruckner Lecture Notes [ 5. Deterministic Space Bounded Graph connectivity Algorithms Jesper Janson] Deterministic Space Bounded Graph connectivity Algorithms Jesper Janson