In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
, a function problem is a
computational problem
In theoretical computer science, a computational problem is one that asks for a solution in terms of an algorithm. For example, the problem of factoring
:"Given a positive integer ''n'', find a nontrivial prime factor of ''n''."
is a computati ...
where a single output (of a
total function
In mathematics, a partial function from a set to a set is a function from a subset of (possibly the whole itself) to . The subset , that is, the '' domain'' of viewed as a function, is called the domain of definition or natural domain o ...
) is expected for every input, but the output is more complex than that of a
decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
. For function problems, the output is not simply 'yes' or 'no'.
Definition
A functional problem
is defined by a
relation over
strings of an arbitrary
alphabet
An alphabet is a standard set of letter (alphabet), letters written to represent particular sounds in a spoken language. Specifically, letters largely correspond to phonemes as the smallest sound segments that can distinguish one word from a ...
:
:
An algorithm solves
if for every input
such that there exists a
satisfying
, the algorithm produces one such
, and if there are no such
, it rejects.
A promise function problem is allowed to do anything (thus may not terminate) if no such
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:
: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
In the Computational complexity theory, theory of computational complexity, the travelling salesman problem (TSP) asks the following question: "Given a list of cities and the distances between each pair of cities, what is the shortest possible ...
, 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 computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
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.
Self-reducibility
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
An oracle is a person or thing considered to provide insight, wise counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. If done through occultic means, it is a form of divination.
Descript ...
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
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
problem is self-reducible. It is conjectured that the
integer factorization problem is not self-reducible, because deciding whether an integer is prime is in P (easy),
while the integer factorization problem is believed to be hard for a classical computer.
There are several (slightly different) notions of self-reducibility.
Reductions and complete problems
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 problems
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 game theory, the Nash equilibrium is the most commonly used solution concept for non-cooperative games. A Nash equilibrium is a situation where no player could gain by changing their own strategy (holding all other players' strategies fixed) ...
in certain strategic games where a solution is guaranteed to exist. In addition, if TFNP contains any FNP-complete problem it follows that
.
See also
*
Decision problem
In computability theory and computational complexity theory, a decision problem is a computational problem that can be posed as a yes–no question on a set of input values. An example of a decision problem is deciding whether a given natura ...
*
Search problem
In computational complexity theory and computability theory, a search problem is a computational problem of finding
an ''admissible'' answer for a given input value, provided that such an answer exists. In fact, a search problem is specified by a b ...
*
Counting problem (complexity)
In computational complexity theory and computability theory, a counting problem is a type of computational problem. If ''R'' is a search problem then
:c_R(x)=\vert\\vert \,
is the corresponding counting function and
:\#R=\
denotes the corre ...
*
Optimization problem
In mathematics, engineering, computer science and economics
Economics () is a behavioral science that studies the Production (economics), production, distribution (economics), distribution, and Consumption (economics), consumption of goo ...
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
{{refend
Computational problems
Functions and mappings