0
$\begingroup$

I'm not sure whether the distinction between decision and search problems has a deeper significance or if it is just concerns the immediate answer to the problem.

Of course, if you have a finite solution space then you can easily turn a search problem into a decision problem by assigning a 'yes' to whichever output satisfies your conditions. Even if you are searching for the object which maximises some function on the solution space, you can pairwise compare the evaluations of the function to assign 'no' values and be left with the 'yes' solutions.

Perhaps there are search problems cannot be turned into decision problems if we are unable to enumerate the solution space and assign a 'yes' or 'no' to every value?

$\endgroup$
1
$\begingroup$

In terms of decidability, they are equivalent. Indeed, in order to turn a decision problem into a search problem we do the following:

  1. Run the decision algorithm
  2. If it outputted "no", return "no solution exists"
  3. Else, create a list called $Active$, and a counter $w\in\Sigma^*$.
  4. Until you find a solution, repeat the following 5-6 steps:
  5. Create a new instance of an algorithm that checks whether $w$ is a valid solution, and add this instance to $Active$.
  6. For every instance in $Active$, run the algorithm one more step. If any one of them returned "true", return the $w$ associated with it. Otherwise, increase the counter $w$ by one.

Intuitively, the word $w$ enumerates over all $\Sigma^*$, and for each one we check wether it is a valid solution. Since the decision algorithm must have returned "true", there is a valid solution, say $w^*$. Since $w$ enumerates over all $\Sigma^*$, then it will also go through $w^*$ and thus will find the valid solution.


In terms of computation time, the two might differ. It depends on the language itself, and on the granularity of the time complexity you are trying to achieve. For example, $SAT$ has a known search to decision reduction that runs in polynomial time. This means that you can solve the search problem by a polynomial factor of the decision problem. But it wont help you if you are looking for a sub-polynomial factor instead.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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