June 30, 2014

Why do we need better algorithms?

This is the most fundamental question every student must ask himself before taking a course on Algorithms. Rather than talking too much about algorithms let me straight away give examples. All the shown examples are from the speech 'Beyond Computation - Michael Sipser'
Problem 1: Finding the factorial of a large number.
We still don't know whether there is any other possible way to find the solution or not.
Problem 2: Finding the largest clique in a given graph with 100 nodes
But trying to find a large clique in the below figure is very difficult for the computer.
Solution: Trying to find the analogy of magnet in mathematics
If you can find the magnet, you are one of the most Intelligent on the planet.
Other Problems:
So you can see that the biggest challenge is 
This is the ultimate reason why we need better algorithms.
To understand more, let me show you the difference between P and NP problems
If P = NP is proved, then we do not need to search for a search algorithm else we need to search. Whether P = NP or P != NP is a mystery.

NP-Completeness
This is the first step taken by humans towards solving an NP problem. NP-Completeness defines that a set of problems are linked to each other and can be easily transformed into each other which means if there is a solution to one problem, then the solution for the other can be found but the reverse is not true. Eg: Factoring can be converted into CLIQUE but not CLIQUE into Factoring

NP-Hard:
There are NP problems for which even checking is not possible. These are called NP-Hard. Eg of such a problem is Chess.

Will it ever be solved?

No comments:

Post a Comment