Open main menu

In computational complexity theory, a function problem is a computational problem where a single output (of a total function) 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'.

Contents

Formal definitionEdit

A functional problem   is defined as a relation   over strings of an arbitrary alphabet  :

 

An algorithm solves   if for every input   such that there exists a   satisfying  , the algorithm produces one such  .

ExamplesEdit

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:

Given a boolean formula   with variables  , find an assignment   such that   evaluates to   or decide that no such assignment exists.

In this case the relation   is given by tuples of suitably encoded boolean formulas and satisfying assignments. While a SAT algorithm, fed with a formula  , 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 classesEdit

Consider an arbitrary decision problem L in the class NP. By the definition of NP, each problem instance x that is answered ‘yes’ has a polynomial-size certificate y which serves as a proof for the ‘yes’ answer. Thus, the set of these tuples (x,y) forms a relation, representing the function problem “given x in L, find a certificate y for x”. This function problem is called the function variant of L; it belongs to the class FNP.

FNP can be thought of as the function class analogue of NP, in that solutions of FNP problems can be efficiently verified (i.e., in polynomial time in terms of the length of the input on a deterministic Turing machine), 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 whose solutions can be constructed in polynomial time.

Self-reducibilityEdit

Observe that the problem FSAT introduced above can be solved using only polynomially many calls to a subroutine which decides the SAT problem: An algorithm can first ask whether the formula   is satisfiable. After that the algorithm can fix variable   to TRUE and ask again. If the resulting formula is still satisfiable the algorithm keeps   fixed to TRUE and continues to fix  , otherwise it decides that   has to be FALSE and continues. Thus, FSAT is solvable in polynomial time using an oracle deciding SAT. In general, a problem in NP is called self-reducible if its function variant can be solved in polynomial time using an oracle deciding the original problem. Every NP-complete problem is self-reducible. It is conjectured that the integer factorization problem is not self-reducible.

Reductions and complete problemsEdit

Function problems can be reduced much like decision problems: Given function problems   and   we say that   reduces to   if there exists polynomially-time computable functions   and   such that for all instances   of   and possible solutions   of  , it holds that

  • If   has an  -solution, then   has an  -solution.
  •  

It is therefore possible to define FNP-complete problems analogous to the NP-complete problem:

A problem   is FNP-complete if every problem in FNP can be reduced to  . The complexity class of FNP-complete problems is denoted by FNP-C or FNPC. Hence the problem FSAT is also an FNP-complete problem, and it holds that   if and only if  .

Total function problemsEdit

The relation   used to define function problems has the drawback of being incomplete: Not every input   has a counterpart   such that  . Therefore the question of computability of proofs 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 problem it follows that  .

See alsoEdit

ReferencesEdit

  • Raymond Greenlaw, H. James Hoover, Fundamentals of the theory of computation: principles and practice, Morgan Kaufmann, 1998, ISBN 1-55860-474-X, p. 45-51
  • Elaine Rich, Automata, computability and complexity: theory and applications, Prentice Hall, 2008, ISBN 0-13-228806-0, section 28.10 "The problem classes FP and FNP", pp. 689–694