Complexity class
In computational complexity theory, the complexity class FP is the set of function problems that 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.
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 reductions, which are used in turn to define the class of NP-complete problems.
Formal definition.
FP is formally defined as follows:
A binary relation formula_1 is in FP if and only if there is a deterministic polynomial time algorithm that, given formula_2, either finds some formula_3 such that formula_1 holds, or signals that no such formula_3 exists.
References.
 ;templatestyles src="Reflist/styles.css" / ;