FP (Complexity)

In computational complexity theory, FP is the complexity class of function problems solvable by a deterministic Turing machine in polynomial time, where the underlying predicate is also decidable in polynomial time; it is the function-problem counterpart of the decision-problem class P. Where a problem in P produces only a single yes or no bit as its answer, a problem in FP can produce any output computable in polynomial time, so a task such as adding two numbers belongs to FP while the narrower task of deciding whether their sum is odd belongs to P; every decision problem in P can therefore be viewed as a function outputting 0 or 1, making P a subset of FP. Polynomial-time function problems in FP are fundamental to defining polynomial-time reductions, which in turn define the class of NP-complete problems. This description is adapted from Wikipedia contributors under CC BY-SA 4.0; changes were made. https://creativecommons.org/licenses/by-sa/4.0/