5
$\begingroup$

I can say that $x * y$ is a problem, but I can also say that $x * y$ is an algorithm for finding a rectangle area.

I have been reading Wikipedia about an algorithm and a problem, but I am not sure about their definitions. Could you please explain it to me in more detail?

$\endgroup$
2
  • $\begingroup$ I think it also worth noting that for some problems there exist no algorithms. IMHO, this might make the distinction more clear. $\endgroup$
    – Daniil
    Dec 8, 2013 at 9:48
  • $\begingroup$ What’s the difference between a question and an answer? $\endgroup$
    – gnasher729
    Feb 4, 2021 at 17:47

4 Answers 4

6
$\begingroup$

"What is the product of $x$ and $y$?" is a problem, and it might model or correspond to the problem of calculating the area of a rectangle. However, how do you actually compute $x \times y$? An algorithm, informally a precise list of steps to take, for doing this would be some multiplication algorithm.

Another example, from your favorite world of satisfiability is the following problem.

Instance: a 2-CNF formula $\phi$. Question: Is the formula $\phi$ satisfiable?

A method of deciding the problem is an algorithm, such as the truth table method (or a polynomial-time algorithm, such as the ones on Wikipedia).

$\endgroup$
2
  • $\begingroup$ Does Instance and Question are ingredients of the Problem or Instance is the Input and Question is the Problem? $\endgroup$ Dec 7, 2013 at 14:51
  • 1
    $\begingroup$ @Babibu For example, an instance of the multiplication problem could be $x=2$ and $y=3$, and the question would then be: "what is 2 times 3?" Both of these are ingredients of a problem if you will. $\endgroup$
    – Juho
    Dec 7, 2013 at 15:38
8
$\begingroup$

A problem is a thing that needs to be done; an algorithm is a procedure for doing it.

To address your specific example, "What is $x\times y$?" is a problem and "Multiply the length by the width" is an algorithm for solving the problem, "What is the area of this rectangle?" It uses, as a subroutine, some unstated algorithm for multiplying numbers.

$\endgroup$
3
$\begingroup$

As Juho explained in his answer, an algorithm can be seen as a precise list of steps to solve a given problem. A consequence is that the description of the problem and of its solution frequently have to be more precise for an algorithm than for its mere mathematical formulation. Let me illustrate this difference on your example. In mathematics, you would say

Problem: What is the surface of a rectangle of length $x$ and width $y$?
Answer: $xy$

Now, depending on the size of the numbers and the way they are given, different algorithms can be proposed. In order to describe an algorithm to solve the same problem, your may need extra information on the numbers: are the numbers represented as decimal numbers or as binary numbers (as often on a computer), how many digits or bits are used to represent these numbers, etc. Next, you have to explain carefully how you perform the multiplication of two numbers. The page multiplication algorithms suggested by Juho gives plenty of examples. But again, you may need some further information: are you using a single processor or several ones? Sequentially or in parallel? Do you have any restriction on the available memory? Which kind of basic operations can your computer perform?, etc?

Thus in general, an algorithm has to include much more details than a mathematical solution.

$\endgroup$
0
$\begingroup$

While I do agree with the previous answers, which I will not repeat here, I feel there is a dimension that is missing, or at least left implicit. I think it should be explicited.

You could have the problem of finding the product of 222 by 333 for some purpose. In that case, all you need is an answer (73926). Why bother with complicated explanation as to why that is the product? (assuming you can trust your source for the answer)

In general, an algorithm addresses a family of problem, such as: "given two integers $x$ and $y$ (with such and such representation), how do I compute (a representation of) the product $x\times y$. The algorithm can then be used to solve all the problems in the family, one of them being the product of 222 by 333.

The interest of algorithms actually stems from the fact that they solve a whole family of problems. This is remindful of the chinese proverb "Give a man a fish he will eat for a day. Teach a man to fish he will eat for a lifetime".

The fact that algorithms address families of problems is the source of many of the concepts of the study of algorithms such as decidability (is there an algorithm that solves all the problems in the family) or complexity (what is the cost in time, memory, or some other relevant unit) of applying the algorithm, given some measure of the size of the input, i.e., of the parameters of the family.

$\endgroup$

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.