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.

$\endgroup$
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$.

$\endgroup$
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$.

$\endgroup$
  • $\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 '12 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.

$\endgroup$
  • $\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 '12 at 11:03

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.