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:
“It is not growing like a tree
In bulk, doth make man better be,
Or standing long an oak, three hundred year,
To fall a log at last, dry, bald, and sere:
A lily of a day
Is fairer far in May
Although it fall and die that night;
It was the plant and flower of light.
In small proportions we just beauties see,
And in short measures life may perfect be.”
—Ben Jonson (1572–1637)
“Though seas and land be ‘twixt us both,
Our faith and troth,
Like separated souls,
All time and space controls:
Above the highest sphere we meet
Unseen, unknown, and greet as angels greet.”
—Richard Lovelace (1618–1658)
“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)