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 = CoSL.
Read more about this topic: Symmetric Turing Machine
Famous quotes containing the words log, space and/or complexity:
“This state is full of these log cabin Abe Lincolns with price tags on ‘em. The louder he yells, the higher his price.”
—Robert Rossen (1908–1966)
“Time in his little cinema of the heart
Giving a première to Hate and Pain;
And Space urbanely keeping us apart.”
—Philip Larkin (1922–1986)
“It is not only their own need to mother that takes some women by surprise; there is also the shock of discovering the complexity of alternative child-care arrangements that have been made to sound so simple. Those for whom the intended solution is equal parenting have found that some parents are more equal than others.”
—Elaine Heffner (20th century)