Number of ways to solve a problem

[Avichal]

This probably belongs to a computer science or a psychology thread.

I was thinking if we can count the number of ways we can solve a problem.
To do that we may have to define the problem and the steps you can do precisely.
So let's say that the problem is a computational problem and the steps you can do is what a computer can do (or what a turing machine can do)

Now is it theoritically possible to count the number of ways to solve the problem? Even a simple problem like sorting has so many algorithms? Is there a limit to number of ways to solve it?

This question has been strangely bugging me recently

 

[DavidSnider]

I think you would need a more rigorous definition of what constitutes a "way" and a "problem".

You could just randomly swap elements until the list is sorted. There are ways to count the number of possible unique paths this could take, but it would be practically meaningless.

 

[Avichal]

Its tough to think about a rigorous definition of a "way" and a "problem".
But take the example of sorting a sequence of numbers. We know it's a "problem". And there are many "ways" to solve it.
E.g.:- quicksort, mergesort, bogosort(randomly swapping) etc.
So we know many "ways" to do it? Is there a limit to it?

What I think is:- Since we have finite number of operations like swapping, comparing we can do, surely there must be finite number of ways to solve the problem.

Any thoughts?

 

[godzillabill]

Solve x-1=0 for x

One solution:
add 1 to both sides, getting x=1

Second solution:
add 2 to both sides, getting x+1=2
subtract 1, getting x=1

Third:
add 3 to both sides, etc etc etc

 

[Borek]

Borek's law: There always exist a more convoluted solution.

 

[256bits]

What I think is:- Since we have finite number of operations like swapping, comparing we can do, surely there must be finite number of ways to solve the problem.

Truth be told, the number of ways is infinite, or a very large number.

If you want to decrease that number, then you will have to add some caveats in terms of efficiency of operations, such as minimum number of steps required.

 

[Avichal]

I somehow feel troubled by the fact that there are infinitely many ways to solve a problem.
I cannot understand why a simple problem say sorting can have infinite number of algorithms.

 

[ZombieFeynman]

I somehow feel troubled by the fact that there are infinitely many ways to solve a problem.
I cannot understand why a simple problem say sorting can have infinite number of algorithms.

Many problems have an infinite ways of solving them... and an infinite number of those ways are bad.

Suppose I live on a 2D Euclidean isotropic, infinite plane. I place my origin at my starting location and I wish to end at some point P = (a,b). Now, clearly the best way of getting there ( if we define best by the shortest route ) is via the straight line joining (0,0) and (a,b). But there are an infinite ways of getting to P. I could walk randomly until I get there, or walk to (a,0) along the x-drection and then walk down to (a,-d) and up to P, or along a circular segment of radius R joining (0,0) and P, or...

You can see that not only is the number of solutions to my walking problem infinite, it is uncountably infinite on my idealized 2D manifold! Why is it difficult to imagine similar circumstances with other types of (less trivial) problems?

 

[Avichal]

Well that way yes, there are infinite ways. I get it.

But let's say we have to reach our goal in some particular amount of steps or time. Then are there infinite solutions or not?
In your problem i.e. going from one place to another. If you are allowed finite amount of steps then there should be some finite amount of ways to do it.

Similarly, say for sorting, if we allow only an nlogn solution, then are there finite number of ways to do it?

 

[D H]

Similarly, say for sorting, if we allow only an nlogn solution, then are there finite number of ways to do it?

One of the key operations in a sorting algorithm is to swap elements. Swapping twice restores the to-be swapped elements to their original locations. Swapping three times, or five times, or any odd number of times has the same effect as a single swap. But replacing that swap with three swaps is a different algorithm. Adding two more and it's yet another algorithm. And so on. There are an infinite number of such swap an odd number of times algorithms. If the original swap-once algorithm was O(n*log n), so are all of those swap an odd number of times algorithms.

 

[Borek]

If you are allowed finite amount of steps then there should be some finite amount of ways to do it.

Let's say you have to go from point A to point B in two steps. For simplicity, the distance is 1. In how many ways can you split the distance into two steps?

It doesn't have to be the same way in the digital world.

 

[AlephZero]

If $n$ is the number of ways that you know how to solve a given problem, the hard part is usually getting from $n = 0$ to $n > 0$.

 

[Avichal]

One of the key operations in a sorting algorithm is to swap elements. Swapping twice restores the to-be swapped elements to their original locations. Swapping three times, or five times, or any odd number of times has the same effect as a single swap. But replacing that swap with three swaps is a different algorithm. Adding two more and it's yet another algorithm. And so on. There are an infinite number of such swap an odd number of times algorithms. If the original swap-once algorithm was O(n*log n), so are all of those swap an odd number of times algorithms.

Yes, you can always swap and back again to restore the changes. In this manner, there are infinitely many algorithms. But I was talking about something more general.

It's hard to define what a "way" is but we know quicksort and mergesort are two different algorithms. They do different set of things. Similarly bubblesort is different, heapsort is different etc. They are different approaches to the same problem.
I was asking how many such approaches can there be to a problem as simple as sorting.

 

[FlexGunship]

Perhaps, the number of ways (n) to solve a problem can only be 0 or infinite.

 

[SteamKing]

I somehow feel troubled by the fact that there are infinitely many ways to solve a problem.
I cannot understand why a simple problem say sorting can have infinite number of algorithms.

Just be glad that all problems don't have an infinite number of solutions. There are some problems with no solutions, there are some with a few or many different solutions, and there are just some with an infinite number of solutions.

I wouldn't get too hung up on how many different ways there are to solve a problem as long as I suspect there is at least one way to solve it.