What is an NP-Complete problem?
Posted by archworx on March 15, 2007
So, you must have heard this term before. I had heard it before and was really looking forward to know it. Yesterday I learnt it in my algorithms class. Basically, computer scientists have considered algorithms that execute in polynomial time (n^k) (where n is the size of the problem k is a constant and ^ denotes power) better than those solved in exponential time (k^n) (where k is a constant and n is the size of the problem ^ denotes power). This is a bit intuitive because exponential time algorithms have a tremendous growth rate (as the problem size increases, the time needed to solve it increases exponentially). After this quick introduction lets turn back to NP-complete problems. Strictly, NP-complete problems are defined as a class of problems/algorithms which if one can be solved in polynomial time then all others can be solved in polynomial time, and since people have been unable to prove for more than thirty years that even one of these problems can be solved in polynomial time, it is unlikely (to our current knowledge) that they can be solved in polynomial time. In other words (from my understanding) if a problem is NP-complete then we cannot (to our current knowledge) solve it using an efficient algorithm (one that takes polynomial time). This is because the problem grows very rapidly with increase in input, and is practically unsolvable for large values of n. An example of an NP-complete problem is the well known traveling salesman problem . For more on the issue of NP-completeness read the wikipedia article.