5
$\begingroup$

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

I 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$
  • $\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 '13 at 9:48
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$
  • $\begingroup$ Does Instance and Question are ingredients of the Problem or Instance is the Input and Question is the Problem? $\endgroup$ – Ilya Gazman Dec 7 '13 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 '13 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$
-1
$\begingroup$

I feel a problem is a formal representation of a task that is to be done. Ex. Is there two numbers x and y such that sum is 5 and difference is also 5? This is a problem for it represents a task that is to be done, ie. find two numbers x and y satisfying two other criterion. But this is clearly no algorithm.

An algorithm on the other hand describes how one goes about trying to complete the task (solve the problem). It entails the procedure to the 'solution' of the problem which is of course a separate identity from the 'problem'. Ex. (x+y=5) ^ (x-y=5) => (y=5-x)^(x-y=5) => (y=5-x)^(x-(5-x)=5)=> (y=5-x)^(x=5) => y=0 ^ x=5 The above two numbers satisfy the problem. The algorithm works by trying to represent one variable in another variable and then substituting this value in the other equation to essentially get an answer for one the variables, which again substituted gives the answer to the remaining variable.

As, you can clearly see a problem is quite different from an algorithm! Even though it apparently looks like you are talking about similar things in your confusion above, you are not!

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