FL (complexity)

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.

FL is a subset of FP, the set of function problems which can be solved in deterministic polynomial time.

[1] 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.

[2][3] Similarly one may define FNL, which has the same relation with NL as FNP has with NP.