Editing Function problem (section)

== Definition ==
A functional problem <math>P</math> is defined by a [[Relation (mathematics)|relation]] <math>R</math> over [[String (computer science)|strings]] of an arbitrary [[Alphabet (computer science)|alphabet]] <math>\Sigma</math>:

: <math>R \subseteq \Sigma^* \times \Sigma^*.</math>

An algorithm solves <math>P</math> if for every input <math>x</math> such that there exists a <math>y</math> satisfying <math>(x, y) \in R</math>, the algorithm produces one such <math>y</math>, and if there are no such <math>y</math>, it rejects.

A promise function problem is allowed to do anything (thus may not terminate) if no such <math>y</math> exists.