1
$\begingroup$

Its kind of a weird question to ask but I have been asking myself this: Is there a limit to number of ways to find a solution to a particular problem.

Take the simplest problem: sorting a sequence of numbers.

Now there are a lot of algorithms to sort. Is there a limit to such algorithms? Technically, you can always flip a bit and back again, so there are infinite number of ways.

But still, simple problem as sorting, surely there must be finite number of ways to solve it.

In computer science we have computability theory which tells us whether a problem is solvable, complexity theory which tells us time and space to solve the problem. Similarly, is there something which can tell us the number of ways we can solve a particular problem?

Motivation for this question is that I'm amazed how many sorting algorithms we have. Such a simple problem and there are so many solutions!

Note: I asked this on stackoverflow. It seems that we need to precisely define how we would differentiate between two algorithms. Let's say we do it by somehow recognizing steps that are useless. That way we can say if two algorithms are doing the same thing. What after that? Lets take the example of sorting. All you can do is move one number from one index to other. With just this operation, surely there must be finite number of algorithms to solve the sorting problem

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ Like you say, you might rsetrict the notion of what it means to find a solution. That way you can't have algorithms with arbitrary complexity (I think), since they aren't allowed to do arbitrary useless work. For sorting, this might mean that the worst algorithm might have complexity $O(n!)$ - permutation sort. Checking each permutation if it is sorted and, if not, discarding it, is useful work. I don't know if there are worse sorting algorithms. $\endgroup$ – Guildenstern May 22 '14 at 13:06
  • 1
    $\begingroup$ I'm a bit confused. At first I thought you were talking about the number of solutions, i.e. the size of a search space of a problem. But I guess you are asking about the number of algorithms to solve a certain problem, such as the sorting problem. If you give me an algorithm, I can always modify it so that it does something unnecessary, but still solves the problem. $\endgroup$ – Juho May 22 '14 at 13:08
  • 3
    $\begingroup$ @Guildenstern If you disallow "unnecessary work", doing a brute-force through every possible solution is the slowest deterministic algorithm. You can still do something else too, like this for sorting. $\endgroup$ – Juho May 22 '14 at 13:11
3
$\begingroup$

As far as I can see, there are always infinitely many ways of doing something, even if you try to define and disallow redundant steps. Let's take the example of sorting. Even if you restrict to the operations of comparing and swapping numbers, there are infinitely many ways of sorting a list: quicksort the list; swap the first two numbers and then quicksort; swap the first two numbers twice and then quicksort; ...; swap the first two numbers $n$ times, then quicksort; ...

OK, so you try to disallow that as "wasting time". But then there are still infinitely many ways: quicksort; mergesort if the list has length two, otherwise quicksort; mergesort if the list has length three, otherwise quicksort; ...

OK, so you try to disallow that on grounds that quicksort and mergesort will always produce the same answer so the test on the length of the list is redundant. But this is too coarse a notion of equivalence, since now there's exactly one algorithm for every problem – every correct sorting algorithm produces the same answer by definition.

Improve this answer
$\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.