2
$\begingroup$

From Wikipedia

a computational problem is understood to be a task that is in principle amenable to being solved by a computer (i.e. the problem can be stated by a set of mathematical instructions). Informally, a computational problem consists of problem instances and solutions to these problem instances. For example, primality testing is the problem of determining whether a given number is prime or not. The instances of this problem are natural numbers, and the solution to an instance is yes or no based on whether the number is prime or not.

... A key distinction between analysis of algorithms and computational complexity theory is that the former is devoted to analyzing the amount of resources needed by a particular algorithm to solve a problem, whereas the latter asks a more general question about all possible algorithms that could be used to solve the same problem.

So a problem can be solved by multiple algorithms.

I was wondering if an algorithm can solve different problems, or can only solve one problem? Note that I distinguish a problem and its instances as in the quote.

Improve this question
$\endgroup$

3 Answers 3

Reset to default
4
$\begingroup$

I think the question is more philosophical than scientific, and indeed, as @raphael mentioned, the problem is in the definition of a "Problem".

Algorithm, in the simplest way, is a function (a mapping). It gets an input (instance) $in \in I$ and gives an output $out \in O$. For any instance $in$ there is only a single output $out=\mathsf{ALG}(in)$. Therefore, the algorithm solves only a single problem — that is, it defines only a single mapping from $I$ to $O$.

True, if you have two problems (mappings), $P_1 : I_1 \to O_1$ and $P_2: I_2 \to O_2$ we can construct a "single" algorithm that solves "both". It gets as an input the pair $(in,type)$. If $type=1$ it returns $P_1(in)$ and otherwise it returns $P_2(in)$.

But again, this fancy algorithm can be seen as solving a single problem from the domain $(I_1\cup I_2) \times \{1,2\}$ into $O_1 \cup O_2$.

Improve this answer
$\endgroup$
4
  • $\begingroup$ An algorithm (function) is a mapping (data structure)... which implies function == data? $\endgroup$
    – lifebalance
    Nov 7, 2016 at 17:16
  • $\begingroup$ @lifebalance mapping is a data structure? $\endgroup$
    – Ran G.
    Nov 8, 2016 at 10:47
  • $\begingroup$ How about "Practically everything (including an algorithm, a mapping) is a Graph"? $\endgroup$
    – lifebalance
    Nov 8, 2016 at 13:19
  • 1
    $\begingroup$ @lifebalance everything can be represented by a graph, maybe. $\endgroup$
    – Ran G.
    Nov 8, 2016 at 18:26
2
$\begingroup$

I think this can be answered in a fairly trivial way.

I could easily introduce a tag into the description of a problem and make my algorithm branch on that tag and then call more specific algorithms to solve the actual problem, thereby making an algorithm that solves more than one problem.

For instance, I can tag the input with $1$ if it is an instance of SUBSET-SUM and with a $2$ if it is an instance of HAMILTONIAN-PATH. Then the first step of my algorithm inspects the tag, and runs an algorithm for solving SUBSET-SUM if the tag is a $1$ or runs an algorithm for solving HAMILTONIAN-PATH if the tag is a $2$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ But then, you would have defined a new problem, formally. The notion of "problem" is too slippery; usually, the "real" problem is subtly different from the formal problem we set up to model (and solve) the real one. $\endgroup$
    – Raphael ♦
    Oct 5, 2012 at 11:04
1
$\begingroup$

You can, for example, reduce problem A to a problem B, and then apply the classic algorithm for solving B to A. Therefore I'd say, you can apply algorithms to different problems.

Improve this answer
$\endgroup$
1
  • $\begingroup$ It would be useful if you illustrated your answer with an excample (solving some problem by translating into an LP comes to mind). $\endgroup$
    – Raphael ♦
    Oct 5, 2012 at 11:03

Your Answer

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

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