Science Fair Project Encyclopedia
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.
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.
Last updated: 05-19-2005 02:52:03
10-26-2009 08:16:03
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details
The contents of this article is licensed from www.wikipedia.org under the GNU Free Documentation License. Click here to see the transparent copy and copyright details