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:
“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)
“Someone had literally run to earth
In an old cellar hole in a byroad
The origin of all the family there.
Thence they were sprung, so numerous a tribe
That now not all the houses left in town
Made shift to shelter them without the help
Of here and there a tent in grove and orchard.”
—Robert Frost (1874–1963)
“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)