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. In many senses, this may be the same as set of problems which are efficiently computable on classical computers.

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. The corresponding set of decision problems is P.

Many important open problems in complexity theory relate to the relationships between different resources, such as time and space. We know that a polynomial amount of time is at least the equivalent of a logarithmic amount of memory space. Thus, FP is at least as large as FL, the set of function problems which can be calculated in logspace. However, it is not known whether the two are equal or different. This corresponds to the problem of whether the decision classes P (complexity) and L (complexity) are equal.