In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
, the
complexity class
In computational complexity theory, a complexity class is a set of computational problems of related resource-based complexity. The two most commonly analyzed resources are time and memory.
In general, a complexity class is defined in terms o ...
FP is the set of
function problem
In computational complexity theory, a function problem is a computational problem where a single output (of a total function) is expected for every input, but the output is more complex than that of a decision problem. For function problems, the ...
s that can be solved by a
deterministic Turing machine
A Turing machine is a mathematical model of computation describing an abstract machine that manipulates symbols on a strip of tape according to a table of rules. Despite the model's simplicity, it is capable of implementing any computer alg ...
in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
. It is the function problem version of the
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question of the input values. An example of a decision problem is deciding by means of an algorithm whe ...
class
P. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.
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.
Polynomial-time function problems are fundamental in defining
polynomial-time reduction
In computational complexity theory, a polynomial-time reduction is a method for solving one problem using another. One shows that if a hypothetical subroutine solving the second problem exists, then the first problem can be solved by transforming ...
s, which are used in turn to define the class of
NP-complete problems.
Formal definition
FP is formally defined as follows:
:A
binary relation
In mathematics, a binary relation associates elements of one set, called the ''domain'', with elements of another set, called the ''codomain''. A binary relation over sets and is a new set of ordered pairs consisting of elements in and in ...
is in FP if and only if there is a deterministic polynomial time algorithm that, given
, can find some
such that
holds.
Related complexity classes
*
FNP is the set of binary relations for which there is a polynomial time algorithm that, given ''x'' and ''y'', checks whether P(''x'',''y'') holds. Just as P and FP are closely related, NP is closely related to
FNP. FP = FNP if and only if P = NP.
* 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
External links
Complexity Zoo: FP
{{DEFAULTSORT:Fp (Complexity)
Complexity classes