Function problem explained
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
:
R\subseteq\Sigma* x \Sigma*.
Note that
does not have to be a functional binary relation.
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 permits the algorithm 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:
with variables
, find an assignment
such that
evaluates to
or decide that no such assignment exists.
In this case the relation
is given by pairs of suitably encoded propositional 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 classes
in the class
NP. By the definition of
NP, there is a system of certificates such that each problem instance
that is answered 'yes' has a
polynomial-size certificate
that serves as a proof for the 'yes' answer (and problem instances answered 'no' have no such certificates). Thus, the set of these pairs
forms a relation, representing the function problem "given
in
, find a certificate
for
". This function problem is called a
function variant of
; 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 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
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.
[1] [2] [3] Reductions and complete problems
Function problems can be reduced much like decision problems: Given function problems
and
we say that
reduces to
if there exist polynomially-time computable functions
and
such that for all instances
of
and possible solutions
of
, it holds that
has an
-solution, then
has an
-solution.
(f(x),y)\inS\implies(x,g(x,y))\inR.
It is therefore possible to define FNP-hard problems analogous to NP-hard problems:
A problem
is
FNP-hard if every problem in
FNP can be reduced to
. A problem
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 it holds that
if and only if
.
Total function problems
The relation
used to define function problems has the drawback of being possibly incomplete: Not every input
necessarily has a counterpart
such that
. 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 problem it follows that
.
See also
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
Notes and References
- K.. Ko. On self-reducibility and weak P-selectivity. Journal of Computer and System Sciences. 26. 2. 209–221. 1983. 10.1016/0022-0000(83)90013-2.
- C.. Schnorr. Claus P. Schnorr. Optimal algorithms for self-reducible problems. In S. Michaelson and R. Milner, Editors, Proceedings of the 3rd International Colloquium on Automata, Languages, and Programming. 322–337. 1976.
- A.. Selman. Natural self-reducible sets. SIAM Journal on Computing. 17. 5. 989–996. 1988. 10.1137/0217062 .
