Formally, we define a variant of Turing machines with a set of transitions of the form
The ability to peek at two symbols and change both at a time is non-essential, but makes the definition easier.
Such machines were first defined in 1982 by Harry R. Lewis and Christos Papadimitriou,[1][2] who were looking for a class in which to place USTCON, the problem asking whether there is a path between two given vertices s,t in an undirected graph.
is the class of the languages accepted by a symmetric Turing machine running in time
to an initial stage where a string of symbols is nondeterministically written, followed by deterministic computations.
SSPACE(S(n)) is the class of the languages accepted by a symmetric Turing machine running in space
SL can equivalently be defined as the class of problems logspace reducible to USTCON.
Then, they observed that any language in SL is logspace reducible to USTCON as from the properties of the symmetric computation we can view the special configuration as the undirected edges of the graph.
In 2004, Omer Reingold proved that SL=L by showing a deterministic algorithm for USTCON running in logarithmic space,[3] for which he received the 2005 Grace Murray Hopper Award and (together with Avi Wigderson and Salil Vadhan) the 2009 Gödel Prize.