# FP (complexity)

In computational complexity theory, the complexity class **FP** is the set of function problems which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem class **P**. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.

**FP** is formally defined as follows:

- A binary relation P(
*x*,*y*) is in**FP**if and only if there is a deterministic polynomial time algorithm that, given*x*, can find some*y*such that P(*x*,*y*) holds.

The difference between **FP** and **P** is that problems in **P** have one-bit, yes/no answers, while problems in **FP** can have any output that can be computed in polynomial time. For example, adding two numbers is an **FP** problem, while determining if their sum is odd is in **P**.

Just as **P** and **FP** are closely related,
**NP** is closely related to **FNP**.

Polynomial-time function problems are fundamental in defining polynomial-time reductions, which are used in turn to define the class of NP-complete problems.

Because a machine that uses logarithmic space has at most polynomially many configurations, **FL**, the set of function problems which can be calculated in logspace, is contained in **FP**. It is not known whether **FL** = **FP**; this is analogous to the problem of determining whether the decision classes P and L are equal.

## References[edit]

- Bürgisser, Peter (2000).
*Completeness and reduction in algebraic complexity theory*. Algorithms and Computation in Mathematics.**7**. Berlin: Springer-Verlag. p. 66. ISBN 3-540-66752-0. Zbl 0948.68082. - Rich, Elaine (2008). "28.10 "The problem classes FP and FNP"".
*Automata, computability and complexity: theory and applications*. Prentice Hall. pp. 689–694. ISBN 0-13-228806-0.