**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:

“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)

“The limitless future of childhood shrinks to realistic proportions, to one of limited chances and goals; but, by the same token, the mastery of time and *space* and the conquest of helplessness afford a hitherto unknown promise of self- realization. This is the human condition of adolescence.”

—Peter Blos (20th century)

“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)