Editing FL (complexity) (section)

In [[computational complexity theory]], the [[complexity class]] '''FL''' is the set of [[function problem]]s which can be solved by a [[deterministic Turing machine]] in a [[logarithm]]ic amount of [[Memory space (computational resource)|memory space]].<ref name="abj">{{citation|contribution=Functional oracle queries as a measure of parallel time|first1=Carme|last1=Àlvarez|first2=José L.|last2=Balcázar|first3=Birgit|last3=Jenner|title=STACS 91|series=Lecture Notes in Computer Science|volume=480|year=1991|pages=422–433|publisher=Springer|doi=10.1007/BFb0020817|hdl=2117/327984|isbn=3-540-53709-0 |hdl-access=free}}.</ref> As in the definition of [[L (complexity)|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 problem]]s, which produce only Yes or No answers and corresponds to the set '''[[L (complexity)|L]]''' of [[decision problem]]s which can be solved in deterministic logspace.  '''FL''' is a subset of '''[[FP (complexity)|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>{{citation|first1=A.|last1=Chiu|first2=G.|last2=Davida|first3=B.|last3=Litow|title=Division in logspace-uniform NC1|journal=RAIRO Theoretical Informatics and Applications|volume=35|pages=259–276|year=2001|issue=3 |doi=10.1051/ita:2001119 }}.</ref><ref>{{citation|contribution-url=http://ftp.cs.rutgers.edu/pub/allender/division.eatcs.pdf|contribution=The division breakthroughs|first=Eric|last=Allender|authorlink=Eric Allender|title=Current Trends in Theoretical Computer Science|publisher=World Scientific|year=2004|pages=147–164}}.</ref>

Similarly one may define '''FNL''', which has the same relation with [[NL (complexity)|NL]] as [[FNP (complexity)|FNP]] has with [[NP (complexity)|NP]].<ref name="abj"/>