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.[1] 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.[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.[1]
References
- ↑ 1.0 1.1 1.2 Àlvarez, Carme; Balcázar, José L.; Jenner, Birgit (1991), "Functional oracle queries as a measure of parallel time", STACS 91, Lecture Notes in Computer Science, 480, Springer, pp. 422–433, doi:10.1007/BFb0020817.
- ↑ Chiu, A.; Davida, G.; Litow, B. (2001), "Division in logspace-uniform NC1", RAIRO Theoretical Informatics and Applications 35: 259–276.
- ↑ Allender, Eric (2004), "The division breakthroughs", Current Trends in Theoretical Computer Science, World Scientific, pp. 147–164, http://ftp.cs.rutgers.edu/pub/allender/division.eatcs.pdf.
 |  |
