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 complexity, space and/or log:
“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)
“To play is nothing but the imitative substitution of a pleasurable, superfluous and voluntary action for a serious, necessary, imperative and difficult one. At the cradle of play as well as of artistic activity there stood leisure, tedium entailed by increased spiritual mobility, a horror vacui, the need of letting forms no longer imprisoned move freely, of filling empty time with sequences of notes, empty space with sequences of form.”
—Max J. Friedländer (1867–1958)
“My merrie, merrie boyes,
The Christmas Log to the firing;”
—Robert Herrick (1591–1674)