Editing Function problem (section)

== 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 [[Boolean satisfiability problem|'''SAT''']] decision problem, can be formulated as follows:

:Given a boolean formula <math>\varphi</math> with variables <math>x_1, \ldots, x_n</math>, find an assignment <math>x_i \rightarrow \{ \text{TRUE}, \text{FALSE} \}</math> such that <math>\varphi</math> evaluates to <math>\text{TRUE}</math> or decide that no such assignment exists.

In this case the relation <math>R</math> is given by tuples of suitably encoded boolean formulas and satisfying assignments.
While a SAT algorithm, fed with a formula <math>\varphi</math>, 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.