Function Problem

Get Function Problem essential facts below. View Videos or join the Function Problem discussion. Add Function Problem to your PopFlock.com topic list for future reference or share this resource on social media.
## Formal definition

## Examples

## Relationship to other complexity classes

## Self-reducibility

## Reductions and complete problems

## Total function problems

## See also

## References

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Function Problem

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'.

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 .

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.

Consider an arbitrary decision problem in the class **NP**. By the definition of **NP**, each problem instance that is answered 'yes' has a polynomial-size certificate which serves as a proof for the 'yes' answer. Thus, the set of these tuples forms a relation, representing the function problem "given in , find a certificate for ". This function problem is called the *function variant* of ; 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 (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 whose solutions can be found in polynomial time.

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^{[by whom?]} that the integer factorization problem is not self-reducible.

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 .

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 .

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. (October 2015) (Learn how and when to remove this template message) |

- 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

This article uses material from the Wikipedia page available here. It is released under the Creative Commons Attribution-Share-Alike License 3.0.

Popular Products

Music Scenes

Popular Artists