FP (complexity class)

In theoretical computer science, especially complexity theory , the class FP describes the set of all search problems that can be solved by a deterministic Turing machine in polynomial time ( English function polynomial time , hence the abbreviation). Put simply, these are all search problems that can be efficiently solved on a classic computer.

definition

A left total relation is in FP if there is a deterministic algorithm that calculates a given in polynomial time , so that . ${\displaystyle P\subseteq X\times Y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle P(x,y)}$

It restricts additionally quite clear relations and to truth values, you get exactly the complexity class P . ${\displaystyle P}$ ${\displaystyle Y}$

Analogous to the class NP , a more general class can define FNP . The only requirement for elements in this class is that it can be determined deterministically for a given pair of values in polynomial time whether the following applies. ${\displaystyle x,y}$ ${\displaystyle P(x,y)}$

Web links

• FP . In: Complexity Zoo. (English)