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. For function problems, the output is not simply 'yes' or 'no'.

Definition

A function problem is defined by a relation over strings of an arbitrary alphabet:

does not have to be a functional binary relation.

An algorithm, it rejects.

A promise function problem exists.

Examples

A well-known function problem is given by the functional Boolean satisfiability problem, FSAT for short. The problem, which is closely related to the SAT decision problem, can be formulated as follows:

1. Given a propositional formula or decide that no such assignment exists.

, only needs to return "unsatisfiable" or "satisfiable", an FSAT algorithm needs to return some satisfying assignment in the latter case.

Other notable examples include the travelling salesman problem, which asks for the route taken by the salesman, and the integer factorization problem, which asks for the list of factors.

Relationship to other complexity classes

Consider an arbitrary decision problem in the class NP. By the definition of NP that is answered 'yes' has a polynomial". This function problem is called a function variant; it belongs to the class FNP.

Conversely, every problem R in FNP induces a (unique) corresponding decision problem: given x, decide if there exists some y such that R(x,y) holds.

FNP can be thought of as the function class analogue of NP, in that solutions of FNP problems can be efficiently (i.e., in polynomial time in terms of the length of the input) verified, but not necessarily efficiently found. In contrast, the class FP, which can be thought of as the function class analogue of P, consists of function problems for which solutions can be found in polynomial time.

Self-reducibility

Observe that the problem FSAT introduced above can be solved using only polynomially many calls to a subroutine that decides the SAT has to be FALSE and continues. Thus, FSAT is solvable in polynomial time using an oracle deciding SAT. In general, a problem in FNP is called self-reducible if it can be solved in polynomial time using an oracle for its induced decision problem. Every function variant of every NP-complete problem is self-reducible. There are several (slightly different) notions of self-reducibility.

Reductions and complete problems

Function problems can be reduced, it holds that

• -solution.

It is therefore possible to define FNP-hard problems analogous to NP-hard problems:

is FNP-hard if every problem in FNP is FNP-complete if it is FNP-hard and in FNP. The problem FSAT is an FNP-complete problem, and hence by self-reducibility of FSAT.

Total function problems

. Therefore the question of computability of outputs is not separated from the question of their existence. To overcome this problem it is convenient to consider the restriction of function problems to total relations yielding the class TFNP as a subclass of FNP. This class contains problems such as the computation of pure Nash equilibria in certain strategic games where a solution is guaranteed to exist. In addition, if TFNP contains any FNP-complete.

See also

• Decision problem

• Search problem

• Counting problem (complexity)

• Optimization problem

References

• Raymond Greenlaw, H. James Hoover, Fundamentals of the theory of computation: principles and practice, Morgan Kaufmann, 1998, , p.45-51

• Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, , section 28.10 "The problem classes FP and FNP", pp.689–694