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.


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


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'?

  • 3
    $\begingroup$ I think terms like "search problem" and "decision problem" are well defined terms that are used consistently as you have defined them. On the other hand, I think "computational problem" is a more general notion and encompasses a host of input-processing tasks (e.g., the task of sampling from a probability distribution that depends on the input). $\endgroup$ Apr 11 '17 at 20:59
  • $\begingroup$ As mentioned by Robin, sampling problems are another example. ​ ​ $\endgroup$
    – user6973
    Apr 12 '17 at 8:43
  • $\begingroup$ I think I see your point. Defining a sampling problem as a search problem: 'finding a sample y of size n of a given distribution D over A' is indeed troublesome. Am I correct that the fundamental issue is that 'a collection of n elements of A' cannot be simply defined as an (un)acceptable solution, rather it has some likelihood of being correct? $\endgroup$
    – Michigan
    Apr 12 '17 at 8:53
  • 1
    $\begingroup$ No, this is not the issue, there is no likelihood of being correct. The issue is that, in a sampling problem, "correctness" is a property of the probability distribution on outputs, and not of any particular solution. $\endgroup$ Apr 14 '17 at 1:43
  • $\begingroup$ Indeed that makes much more sense. So the 'property to satisfy' rather than being defined on elements of X and Y, is defined on the sets X and Y. Is my example (in comments to the question below) proper? A simpler example would be 'the problem of computing a bijection'. Also, I feel there is a link here with higher order/fuzzy logic (~ 'any problem which can be modeled using first order boolean logic = search problem'?), although this might warrant a new question (which is 'research-level', or whatever that means). $\endgroup$
    – Michigan
    Apr 14 '17 at 7:37

The linked PDF, "Handout 2 for Stanford University — CS254: Computational Complexity", defines four types of "computational problems":

  1. Decision problems

  2. Search problems

  3. Optimization problems

  4. Counting problems

As the document notes at the beginning, it focuses on the first two: decision and search problems.

In this course we will deal with four types of computational problems: decision problems, search problems, optimization problems, and counting problems. For the moment, we will discuss decision and search problem.

However, the document seems to talk about decision problems and search problems as though they were conceptually distinct from each other. It also fails to mention the mapping between them, which is simple and commonly known (PlanetMath):

A relation $R$ can be viewed as a search problem, and a Turing machine which calculates $R$ is also said to solve it. Every search problem has a corresponding decision problem, namely $L(R)=\{x\mid\exists yR(x,y)\}$.

In short, you're correct to realize that decision and search problems are two sides of the same coin. You're also correct that it's weird that the document doesn't appear to mention this obvious fact.

Personally, I'd tend to see these terms differing in connotation. This is, while they can often be mapped to each other, referring to a particular problem as one type rather than another suggests a perspective on how to see that problem, rather than asserts that that problem can't be cast to another type.

  • $\begingroup$ I understand that referring to a certain definition implies a certain 'perspective' on a computational problem, but it also defines a collection of problems ('that can be cast as such'). When surveying literature I frequently came accros statements like "each search problem has an associated decision problem" (e.g. your example: does x have a solution?), however, these are 'has a' relationships not 'is a'. My question was "is there any computational problem which is not a search problem", i.e. 'cannot be cast as such'. One candidate would be the (non-exact) optimization problem (see my edit). $\endgroup$
    – Michigan
    Apr 12 '17 at 8:19
  • $\begingroup$ @Michigan "is there any computational problem which is not a search problem" If you just wrap any problem $\text{A}$ in "Find an answer to $\text{A}$", it seems to be pretty easy to construct a search problem. Not requiring an optimization problem to yield a globally optimal solution doesn't change this; in such a case, you're just replacing proof of global optimality with the convergence criteria. This is, you're asking, "Find an answer that satisfies these convergence criteria" rather than "Find an answer that optimizes this expression". $\endgroup$
    – Nat
    Apr 12 '17 at 18:21
  • $\begingroup$ How about the sampling problem Robin and Ricky mentioned in the comments? Furthermore, my non-exact optimization problem refers to problems where there are no boolean 'convergence criteria', but rather a fuzzy concept 'this solution is more desirable than that one'. Again I feel as long as you think of inputs in terms of problem instances having/no having 0, 1 or more acceptable outputs everything can be put as a search problem. However, there are various 'problems solved using computation' that do not adhere this strict definition. $\endgroup$
    – Michigan
    Apr 13 '17 at 10:36
  • $\begingroup$ @Michigan Digital computers use 0's and 1's, so how could you ever make a computer program that can't be represented in this way? At most, you can try to overlook the fact that it's 0's and 1's, but you can't make it stop being 0's and 1's. $\endgroup$
    – Nat
    Apr 13 '17 at 10:45
  • $\begingroup$ I agree, but I think you misunderstood me. A computational problem is a specification of what a machine is supposed to do (in terms of input/output) to solve that problem (agreed?). For search problems, a given machine either solves it or not (black/white). Arguably, we'd like to model problems which recognize more 'shades of grey' (same way fuzzy logic extends boolean logic) in which case one machine might solve the fuzzy problem 'better' than another according to some well-defined 'desirability' criterion (specified as part of the problem description), e.g. non-exact optimization. $\endgroup$
    – Michigan
    Apr 13 '17 at 13:31

Not the answer you're looking for? Browse other questions tagged or ask your own question.