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

[edit]

1. ^ a b c À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, vol. 480, Springer, pp. 422–433, doi:10.1007/BFb0020817, hdl:2117/327984, ISBN 3-540-53709-0.
2. ^ Chiu, A.; Davida, G.; Litow, B. (2001), "Division in logspace-uniform NC1", RAIRO Theoretical Informatics and Applications, 35 (3): 259–276, doi:10.1051/ita:2001119.
3. ^ Allender, Eric (2004), "The division breakthroughs" (PDF), Current Trends in Theoretical Computer Science, World Scientific, pp. 147–164.

* v
* t
* e

Complexity classes

Considered feasible|

* DLOGTIME
* AC0
* ACC0
* TC0
* L
* SL
* RL
* FL
* NL
* NL-complete
* NC
* SC
* CC
* P
* P-complete
* ZPP
* RP
* BPP
* BQP
* APX
* FP

Suspected infeasible|

* UP
* NP
* NP-complete
* NP-hard
* co-NP
* co-NP-complete
* TFNP
* FNP
* AM
* QMA
* PH
* ⊕P
* PP
* #P
* #P-complete
* IP
* PSPACE
* PSPACE-complete

Considered infeasible|

* EXPTIME
* NEXPTIME
* EXPSPACE
* 2-EXPTIME
* ELEMENTARY
* PR
* R
* RE
* ALL

Class hierarchies|

* Polynomial hierarchy
* Exponential hierarchy
* Grzegorczyk hierarchy
* Arithmetical hierarchy
* Boolean hierarchy

Families of classes|

* DTIME
* NTIME
* DSPACE
* NSPACE
* Probabilistically checkable proof
* Interactive proof system

List of complexity classes

P ≟ NP |

This theoretical computer science–related article is a stub. You can help Wikipedia by expanding it.

|

* v
* t
* e

*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template