linguistic:translation, structural:scholar_edition
Function problems

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, the output is not just yes or no. Notable examples include the traveling salesman problem and the integer factorization problem.

It is tempting to think that the notion of function problems is much richer than the notion of decision problems. However, this is not really the case, since function problems can be recast as decision problems. For example, the multiplication of two integers can be expressed as the set of triples (a, b, c) {\displaystyle (a,b,c)} such that the relation a × b = c {\displaystyle a\times b=c} holds. Deciding whether a given triple is a member of this set corresponds to solving the problem of multiplying two numbers.