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)
“The essence of morality is a questioning about morality; and the decisive move of human life is to use ceaselessly all light to look for the origin of the opposition between good and evil.”
—Georges Bataille (1897–1962)