FP (complexity)
Encyclopedia
In computational complexity theory
, the complexity class
FP is the set of function problem
s which 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.
FP is formally defined as follows:
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. More complex is the relationship between FP and FNP
. FNP is defined as follows:
That is, instead of merely verifying y, the algorithm for solving an FP problem must find its value. This is similar to the computation/verification relationship between P and NP; it also shows that FP is contained in FNP. In fact, FP = FNP if and only if P = NP.
Polynomial-time function problems are fundamental in defining polynomial-time reduction
s, which are used in turn to define the class of NP-complete
problems.
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.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
FP is the set of function problem
Function problem
In computational complexity theory, a function problem is a computational problem where a single output is expected for every input, but the output is more complex than that of a decision problem, that is, it isn't just YES or NO...
s which can be solved by a deterministic Turing machine in polynomial time; it is the function problem version of the decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
class P
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
. Roughly speaking, it is the class of functions that can be efficiently computed on classical computers without randomization.
FP is formally defined as follows:
- A binary relation P(x,y) is in FP if and only if there is a deterministic polynomial time algorithm that, given x, can find some y such that P(x,y) holds.
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. More complex is the relationship between FP and FNP
FNP (complexity)
In computational complexity theory, the complexity class FNP is the function problem extension of the decision problem class NP. The name is somewhat of a misnomer, since technically it is a class of binary relations, not functions, as the following formal definition explains:This definition does...
. FNP is defined as follows:
- A binary relationBinary relationIn mathematics, a binary relation on a set A is a collection of ordered pairs of elements of A. In other words, it is a subset of the Cartesian product A2 = . More generally, a binary relation between two sets A and B is a subset of...
P(x,y), where y is at most polynomially longer than x, is in FNP if and only if there is a deterministic polynomial time algorithm that can determine whether P(x,y) holds given both x and y.
That is, instead of merely verifying y, the algorithm for solving an FP problem must find its value. This is similar to the computation/verification relationship between P and NP; it also shows that FP is contained in FNP. In fact, FP = FNP if and only if P = NP.
Polynomial-time function problems are fundamental in defining polynomial-time reduction
Polynomial-time reduction
In computational complexity theory a polynomial-time reduction is a reduction which is computable by a deterministic Turing machine in polynomial time. If it is a many-one reduction, it is called a polynomial-time many-one reduction, polynomial transformation, or Karp reduction...
s, which are used in turn to define the class of NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
problems.
Because a machine that uses logarithmic space has at most polynomially many configurations, FL
FL (complexity)
In computational complexity theory, the complexity class FL is the set of function problems which can be solved by a deterministic Turing machine in a logarithmic amount of memory space...
, 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
P (complexity)
In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
and L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
are equal.