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)
“There are certain books in the world which every searcher for truth must know: the Bible, the Critique of Pure Reason, the Origin of Species, and Karl Marx’s Capital.”
—W.E.B. (William Edward Burghardt)
“The real, then, is that which, sooner or later, information and reasoning would finally result in, and which is therefore independent of the vagaries of me and you. Thus, the very origin of the conception of reality shows that this conception essentially involves the notion of a COMMUNITY, without definite limits, and capable of a definite increase of knowledge.”
—Charles Sanders Peirce (1839–1914)