<p>The linked PDF, "<a href="http://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf" rel="nofollow noreferrer">Handout 2
 for Stanford University — CS254: Computational Complexity</a>", defines four types of "computational problems":</p>

<ol>
<li><p>Decision problems</p></li>
<li><p>Search problems</p></li>
<li><p>Optimization problems</p></li>
<li><p>Counting problems</p></li>
</ol>

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

<blockquote>
  <p>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.</p>
</blockquote>

<p>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 (<a href="http://planetmath.org/node/33425" rel="nofollow noreferrer">PlanetMath</a>):</p>

<blockquote>
  <p>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)\}$.</p>
</blockquote>

<p>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.</p>

<p>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.</p>

CC BY-SA 3.0
2017-04-12T08:19:14.303Z
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).
Michigan
CC BY-SA 3.0
2017-04-12T18:21:18.523Z
@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".
Nat
CC BY-SA 3.0
2017-04-13T10:36:39.907Z
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.
Michigan
CC BY-SA 3.0
2017-04-13T10:45:31.353Z
@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.
Nat
CC BY-SA 3.0
2017-04-13T13:31:24.290Z
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.
Michigan
CC BY-SA 3.0
2017-04-13T14:12:54.233Z
@Michigan Do any of these "fuzzy" modifications prevent the problem from being run on a digital computer?  I mean, you can obfuscate the problem statement in all sorts of ways, describing it as "fuzzy" or "non-exact", but after all is said and done, it's still a program that runs in 0's and 1's, right?  Or did you have something else in mind?
Nat
CC BY-SA 3.0
2017-04-14T07:04:55.443Z
The program still returns 0 and 1's, it is more a matter it solves a given problem in doing so. A search problem is either solved or not (maps each possible input to an admissible solution) while in a non-exact optimization settings one program might solve it better than another. Again whether you consider this part of the problem specification or simply a non-exact solution to a search problem is a matter of perspective (as a computational problems seems to be a conceptual rather than a formal notion).
Michigan
CC BY-SA 3.0
2017-04-14T07:22:04.053Z
Based on the comments to my original question, another example of 'computational problems' which aren't search problems are sampling problems. Where the set of outputs produced by a program, given a set of possible inputs (~higher order logic?) must satisfy some property. An example would be to output 50% of the time '0' and 50% of the time '1', given as input a natural number (seed). Many different algorithms satisfy this property (e.g. return least significant bit of input) although it is impossible to determine on a per input/output basis whether something is correct/wrong.
Michigan
CC BY-SA 3.0
2017-04-11T20:41:37.900Z
2017-04-11T20:48:01.407Z
2017-04-11T20:48:01.407Z
Nat
<p>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.</p>

<p>Concretely, </p>

<p>I have found the following definitions of a <strong>computational problem</strong>:</p>

<p>[source: <a href="http://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf]" rel="nofollow noreferrer">http://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf]</a></p>

<blockquote>
  <p>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.</p>
</blockquote>

<p>[source: <a href="https://en.wikipedia.org/wiki/Computational_problem]" rel="nofollow noreferrer">https://en.wikipedia.org/wiki/Computational_problem]</a></p>

<blockquote>
  <p>A computational problem can be viewed as an infinite collection of
  instances together with a solution for every instance.</p>
</blockquote>

<p>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$.</p>

<p>Under this definition, the subclasses of decision (Y={yes,no}) and function problems (R is a function) make sense.</p>

<p>However, the definitions of a <strong>search problem</strong> (in the same articles) confuse me, as they seem to be equivalent:</p>

<p>[source: cs.stanford.edu]</p>

<blockquote>
  <p>Thus, a search problem is specified by a relation $R \subseteq\{0,1\}^∗\times\{0,1\}^∗$.</p>
</blockquote>

<p>[source: wikipedia.org]</p>

<blockquote>
  <p>a search problem is a type of computational problem represented by a
  binary relation</p>
</blockquote>

<p>[EDIT]</p>

<p>After some reflection, one candidate for being more general than search problems would be <strong>optimization problems that do not have to be solved optimally</strong> (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$.</p>

<p>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.</p>

<p>Is this reasoning sound?</p>

<p>Also, do you know of any sources I can cite (beyond wikipedia, PlanetMath and handouts...) for definitions of 'computational problem' and 'search problem'?</p>

CC BY-SA 3.0
2017-04-11T20:59:55.403Z
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).
Robin Kothari
CC BY-SA 3.0
2017-04-12T08:53:06.967Z
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?
Michigan
CC BY-SA 3.0
2017-04-14T01:43:55.437Z
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.
Sasho Nikolov
CC BY-SA 3.0
2017-04-14T07:37:09.697Z
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).
Michigan
CC BY-SA 4.0
2023-02-07T17:21:11.307Z
This question was mentioned here: https://scicomp.stackexchange.com/a/32707/27325
user1271772
<search-problem>
Is any computational problem a search problem?
Michigan
# Is any computational problem a search problem?

(Asked by: username_0 on 2017-04-11)

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

**Tags:** search-problem
> **Comments:**
> **username_1**: 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).  
> **username_0**: 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?  
> **username_2**: 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.  
> **username_0**: 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).  
> **username_3**: This question was mentioned here: https://scicomp.stackexchange.com/a/32707/27325  

---

## 1 answers

### Answer by username_4 on 2017-04-11. Score: 3

The linked PDF, "[Handout 2
for Stanford University — CS254: Computational Complexity](http://cs.stanford.edu/people/trevisan/cs254-10/lecture02.pdf)", 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](http://planetmath.org/node/33425)):

> 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.

> **Comments:**
> **username_0**: 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).  
> **username_4**: @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".  
> **username_0**: 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.  
> **username_4**: @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.  
> **username_0**: 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.  
> **username_4**: @Michigan Do any of these "fuzzy" modifications prevent the problem from being run on a digital computer?  I mean, you can obfuscate the problem statement in all sorts of ways, describing it as "fuzzy" or "non-exact", but after all is said and done, it's still a program that runs in 0's and 1's, right?  Or did you have something else in mind?  
> **username_0**: The program still returns 0 and 1's, it is more a matter it solves a given problem in doing so. A search problem is either solved or not (maps each possible input to an admissible solution) while in a non-exact optimization settings one program might solve it better than another. Again whether you consider this part of the problem specification or simply a non-exact solution to a search problem is a matter of perspective (as a computational problems seems to be a conceptual rather than a formal notion).  
> **username_0**: Based on the comments to my original question, another example of 'computational problems' which aren't search problems are sampling problems. Where the set of outputs produced by a program, given a set of possible inputs (~higher order logic?) must satisfy some property. An example would be to output 50% of the time '0' and 50% of the time '1', given as input a natural number (seed). Many different algorithms satisfy this property (e.g. return least significant bit of input) although it is impossible to determine on a per input/output basis whether something is correct/wrong.  

---

