Origin
SL was first defined in 1982 by Lewis and Papadimitriou, who were looking for a class in which to place USTCON, which until this time could, at best, be placed only in NL, despite seeming not to require nondeterminism. They defined the symmetric Turing machine, used it to define SL, showed that USTCON was complete for SL, and proved that
where L is the more well-known class of problems solvable by an ordinary deterministic Turing machine in logarithmic space, and NL is the class of problems solvable by nondeterministic Turing machines in logarithmic space. The result of Reingold, discussed later, shows that in fact, when limited to log space, the symmetric Turing machine is equivalent in power to the deterministic Turing machine.
Read more about this topic: SL (complexity)
Famous quotes containing the word origin:
“All good poetry is the spontaneous overflow of powerful feelings: it takes its origin from emotion recollected in tranquillity.”
—William Wordsworth (1770–1850)
“High treason, when it is resistance to tyranny here below, has its origin in, and is first committed by, the power that makes and forever re-creates man.”
—Henry David Thoreau (1817–1862)
“For, though the origin of most of our words is forgotten, each word was at first a stroke of genius, and obtained currency, because for the moment it symbolized the world to the first speaker and to the hearer. The etymologist finds the deadest word to have been once a brilliant picture.”
—Ralph Waldo Emerson (1803–1882)