I was looking for a formal and general definition of a computational problem (and major subclasses thereof e.g. decision, function and search problems). But, given the definitions I have found thus far, I fail to see how the definition of a 'search problem' is any less general than that of a general 'computational problem', as both seem to correspond to an arbitrary binary relationship.Concretely, I have found the following definitions of a computational problem:[source: http://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf]In a computational problem, we are given an input and we want to  return as output a solution satisfying some property: A computational  problem is then described by the property that the output has to  satisfy given the input.[source: https://en.wikipedia.org/wiki/Computational_problem]A computational problem can be viewed as an infinite collection of  instances together with a solution for every instance.I interpret both to imply that a computational problem corresponds to a relation $R \subseteq X \times Y$ between (representations of) problem instances $X$ and (representations of) solutions $Y$.Under this definition, the subclasses of decision (Y={yes,no}) and function problems (R is a function) make sense.However, the definitions of a search problem (in the same articles) confuse me, as they seem to be equivalent:[source: cs.stanford.edu]Thus, a search problem is specified by a relation $R \subseteq\{0,1\}^\times\{0,1\}^$.[source: wikipedia.org]a search problem is a type of computational problem represented by a  binary relation[EDIT]After some reflection, one candidate for being more general than search problems would be optimization problems that do not have to be solved optimally (otherwise they would reduce to 'finding an optimal solution', i.e. a search problem), as they, besides capturing the 'desirability' of a solution, also capture the'desirability' thereof (some preference relation on Y), a concept not corresponding to any $R \in X \times Y$.In general, I would answer my own question as follows:As long as you think of problems in terms of 'acceptable' outputs given inputs, we're dealing with search problems by definition.Once we need to a more subtle ('fuzzy')/general notion than 'acceptability', such as 'desirability' (e.g. non-exact optimization problem above) a binary relation does no longer suffice.Is this reasoning sound?Also, do you know of any sources I can cite (beyond wikipedia, PlanetMath and handouts...) for definitions of 'computational problem' and 'search problem'?
Is any computational problem a search problem?
search problem