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:
“In the woods in a winter afternoon one will see as readily the origin of the stained glass window, with which Gothic cathedrals are adorned, in the colors of the western sky seen through the bare and crossing branches of the forest.”
—Ralph Waldo Emerson (1803–1882)
“All good poetry is the spontaneous overflow of powerful feelings: it takes its origin from emotion recollected in tranquillity.”
—William Wordsworth (1770–1850)
“We have got rid of the fetish of the divine right of kings, and that slavery is of divine origin and authority. But the divine right of property has taken its place. The tendency plainly is towards ... “a government of the rich, by the rich, and for the rich.””
—Rutherford Birchard Hayes (1822–1893)