Function problem

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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, that is, it isn't just YES or NO.

Formal definition[edit]

A functional problem P is defined as a relation R(x,y) over a cartesian product over strings of an arbitrary alphabet \Sigma:

R \subset \Sigma^* \times \Sigma^*

An algorithm A solves P if for every input x the algorithm either produces an output y such that (x, y) \in R or decides that no such y exists.

Examples[edit]

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

Given a boolean formula \varphi with variables x_1, \ldots, x_n, find an assignment x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \} such that \varphi evaluates to \text{TRUE} or decide that no such assignment exists.

In this case the relation R(x, y) is given by tuples of suitably encoded boolean formulas and satisfying assignments.

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[edit]

Consider an arbitrary decision problem in the class NP. By definition each problem instance x
which are answered 'yes' have a certificate y which servers as a proof for the 'yes' answer. Thus, the set of these tuples (x, y) forms a relation. The complexity class derived from this transformation is denoted by \mathbf{F}(\mathbf{NP}) or FNP for short. The mapping of the complexity class P is denoted by FP. The class FP is the set of function problems which can be solved by a deterministic Turing machine in polynomial time, whereas FNP is the set of function problems which can be solved by a non-deterministic Turing machine in polynomial time.

Self-reducibility[edit]

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 \varphi is satisfiable. After that the algorithm can fix variable x_1 to TRUE and ask again. If the resulting formula is still satisfiable the algorithm keeps x_1 fixed to TRUE and continues to fix x_2, otherwise it decides that x_1 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 problems[edit]

Function problems can be reduced much like decision problems: Given function problems \Pi_R and \Pi_S we say that \Pi_R reduces to \Pi_S if there exists polynomially-time computable functions f and g such that for all instances R and S it holds that

(x, g(y)) \in R \quad \Longleftrightarrow \quad (f(x), y) \in S

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

A problem \Pi_R is FNP-complete if every problem in FNP can be reduced to \Pi_R. The complexity class of FNP-complete problems is denoted by FNP-C or FNPC. It coincides with \mathbf{F}(\mathbf{NP}). Hence the problem FSAT is also an FNP-complete problem, and it holds that \mathbf{P} = \mathbf{NP} if and only if \mathbf{FP} = \mathbf{FNP}.

Total function problems[edit]

The relation R(x, y) used to define function problems has the drawback of being incomplete: Not every input x has a counterpart y such that (x, y) \in R. 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. It has been shown that \mathbf{TFNP} = \mathbf{F}(\mathbf{NP} \cap \textbf{co-NP}). In addition, if TFNP contains any FNP-complete problem it follows that \mathbf{NP} = \textbf{co-NP}.

References[edit]

  • 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

See also[edit]