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:
“Why do you see the speck in your neighbor’s eye, but do not notice the log in your own eye?”
—Bible: New Testament, Matthew 7:3.
Jesus.
“This moment exhibits infinite space, but there is a space also wherein all moments are infinitely exhibited, and the everlasting duration of infinite space is another region and room of joys.”
—Thomas Traherne (1636–1674)
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)