Editing Decision problem (section)

==Function problems==
{{main|Function problem}}

Decision problems are closely related to [[function problem]]s, which can have answers that are more complex than a simple ''YES'' or ''NO''.  A corresponding function problem is "given two numbers ''x'' and ''y'', what is ''x'' divided by ''y''?".

A [[function problem]] consists of a [[partial function]] ''f''; the informal "problem" is to compute the values of ''f'' on the inputs for which it is defined.

Every function problem can be turned into a decision problem; the decision problem is just the graph of the associated function.   (The graph of a function ''f'' is the set of pairs (''x'',''y'') such that ''f''(''x'') = ''y''.)  If this decision problem were effectively solvable then the function problem would be as well.  This reduction does not respect computational complexity, however.  For example, it is possible for the graph of a function to be decidable in polynomial time (in which case running time is computed as a function of the pair (''x'',''y'')) when the function is not computable in [[polynomial time]] (in which case running time is computed as a function of ''x'' alone).  The function ''f''(''x'') = 2<sup>''x''</sup> has this property.

Every decision problem can be converted into the function problem of computing the [[indicator function|characteristic function]] of the set associated to the decision problem.   If this function is computable then the associated decision problem is decidable. However, this reduction is more liberal than the standard reduction used in computational complexity (sometimes called polynomial-time many-one reduction); for example, the complexity of the characteristic functions of an [[NP-complete]] problem and its [[co-NP-complete]] [[Complement (complexity)|complement]] is exactly the same even though the underlying decision problems may not be considered equivalent in some typical models of computation.