FL (complexity)

From Wikipedia, the free encyclopedia

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. 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. FL 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.

FL is known to contain several natural problems, including the multiplication of two numbers.

[edit] References

This article does not cite any references or sources. (April 2008) Please help improve this article by adding citations to reliable sources. Unverifiable material may be challenged and removed.