FP (complexity)

In theoretical computer science, especially in complexity theory, the class FP describes (abbreviation of the English: Function Polynomial -Time) the set of all search problems that can be solved by a deterministic Turing machine in polynomial time. In simple terms, these are all search problems that can be solved on a classical computer effectively.

Definition

A left- total relation is in FP if a deterministic algorithm exists, the one calculated at a given in polynomial time, such that.

You Restricts addition to a fairly unique relations and truth values ​​, one obtains exactly the complexity class P.

Analogous to the class NP can define a more general class FNP. For items in this class is only required that can be verified deterministically for a given pair of values ​​in polynomial time if applies.