In computational complexity theory, the complexity class FL is the set of function problems which can be solved by a deterministic Turing machine in a logarithmic amount of memory space.<ref name="abj">Template:Citation.</ref> As in the definition of L, the machine reads its input from a read-only tape and writes its output to a write-only tape; the logarithmic space restriction applies only to the read/write working tape.
Loosely speaking, a function problem takes a complicated input and produces a (perhaps equally) complicated output. Function problems are distinguished from decision problems, which produce only Yes or No answers and corresponds to the set L of decision problems which can be solved in deterministic logspace. FL is a subset of FP, the set of function problems which can be solved in deterministic polynomial time.<ref name="abj"/>
FL is known to contain several natural problems, including arithmetic on numbers. Addition, subtraction and multiplication of two numbers are fairly simple, but achieving division is a far deeper problem which was open for decades.<ref>Template:Citation.</ref><ref>Template:Citation.</ref>
Similarly one may define FNL, which has the same relation with NL as FNP has with NP.<ref name="abj"/>
ReferencesEdit
{{#invoke:Navbox|navbox}}