4
$\begingroup$

An algorithm is a “unambiguous specification of how to solve a class of problems... calculation, data processing and automated reasoning tasks” Are the class of problems an algorithm can solve more abstractly considered decision problems? Is the ultimate reason for a calculation, data processing or automated reasoning to solve a higher decision problem?

Thank you and forgive my ignorance.

Improve this question
$\endgroup$
1

2 Answers 2

Reset to default
4
$\begingroup$

There is a class of problems called decision problems that have an yes/no answer. These problems can be further be classified in decidable, where we have a way to solve them, or undecidable, for which there cannot be or has not been yet discovered a way to solve them.

However, there is another set of problems where we are not interested in a yes/no answer, but rather in a more specific solution. For example, there are optimisation problems, where we are searching for the best value according to some parameters, or counting problems, where we are interested in counting the number of instances where certain property occurs.

To sum it up, decision problems are a specific class of problems, a subset of which can be solved by algorithms. However, algorithms can be used to solve problems in other classes.

Now, given an algorithm for a specific problem, one can solve multiple problems equivalent to the original one (there are ways of "translating" a problem in the terms of another one, and having a solution to one problem means having a solution for all such problems).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you very much for your response. How can I learn more about translating problems i.e. optimization into a decision problem, etc? That is a new concept to me. $\endgroup$
    – ThunderVault
    Commented Jan 7, 2018 at 17:50
  • 1
    $\begingroup$ Usually, "undecidable" means provably can't be solved. A problem whose solution has not been discovered yet, but may possibly be, is not called "undecidable". $\endgroup$
    – Derek Elkins left SE
    Commented Jan 7, 2018 at 19:57
  • $\begingroup$ @DerekElkins I'd say that undecidable always means provably not computable by a Turing machine (with the exception of some mathematicians using it to menan "independent of the given set of axioms"). Any other use of the term in a technical context is just wrong. $\endgroup$
    – David Richerby
    Commented Jan 7, 2018 at 23:19
2
$\begingroup$

First, note that a decision problem has a very specific meaning in the context of algorithms: a decision problem is essentially a question to which the answer is either YES or NO.

An algorithm does not necessarily have to solve a decision problem. We may for instance design a (simple) algorithm to find an element of maximum value from an list. However, in complexity theory, it turns out that a decision problem is often a very convenient form to reason with. The complexity classes P and NP for example are both classes of decision problems.

Because decision problems are useful, we often 'reformulate' a problem as a decision problem. We could for instance ask whether the maximum element in a list has at least the value $M$. This is a decision problem version of our earlier problem and algorithms that solve this decision problem could (usually) be used to solve the original problem.

Improve this answer
$\endgroup$
4
  • $\begingroup$ oh, I see. Are there more general rules of reformulating a problem? Thank you for your elaborate response btw. $\endgroup$
    – ThunderVault
    Commented Jan 7, 2018 at 17:53
  • $\begingroup$ @ThunderVault Well, there are no general rules for this as far as I'm aware, but when the problem is to maximize some value (this is the case in many algorithms), the related decision problem is to test whether it is possible to get the value larger then some $M$. But this isn't that simple in other cases, such as sorting (see also this answer, although ) Finally, I suppose I should add that this 'reformulation' in general is not a formal procedure and just an(other) argument to justify the focus on decision problems. $\endgroup$
    – Discrete lizard ♦
    Commented Jan 7, 2018 at 18:56
  • 1
    $\begingroup$ @ThunderVault Given some algorithm that produces a result represented as a bitstring (usually necessarily by definition), then you can make a decision problem that asks if the $n$th bit of the output of that algorithm is 1. Even Discrete lizard's example is a disguised form of this. If you wanted to find the maximum value of the list given only that you could ask if it was above some value, you'd increase exponentially until you overshot the value, then binary search the interval which corresponds to asking about a bit of the result at a time. $\endgroup$
    – Derek Elkins left SE
    Commented Jan 7, 2018 at 20:05
  • $\begingroup$ @DerekElkins While your procedure is indeed rather general, when applying it you should be careful not to make the decision problem too easy. For example, we may have some problem where the output needs to list some property of exponentially many items. Then, determining a single bit corresponds to testing a single item, which may be a lot easier than the original problem. Of course, this encoding is badly chosen, but I wonder whether an encoding such that the decision problem doesn't become 'too easy' exists for all problems. Can you shed some light on this? $\endgroup$
    – Discrete lizard ♦
    Commented Jan 8, 2018 at 9:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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