10.1 Importance of NP-Completeness

Most algorithms we have studied so far have polynomial-time running times. According to Cormen, Leiserson, and Rivest, polynomial-time algorithms can be considered tractable for the following reasons.

(1)

Although a problem which has a running time of say O(n²⁰) or O(n¹⁰⁰) can be called intractable, there are very few practical problems with such orders of polynomial complexity.

(2)

For reasonable models of computation, a problem that can be solved in polynomial time in one model can also be solved in polynomial time on another.

(3)

The class of polynomial-time solvable problems has nice closure properties (since polynomials are closed under addition, multiplication, etc.)

The class of NP-complete (Non-deterministic polynomial time complete) problems is a very important and interesting class of problems in Computer Science. The interest surrounding this class of problems can be attributed to the following reasons.

1.

No polynomial-time algorithm has yet been discovered for any NP-complete problem; at the same time no NP-complete problem has been shown to have a super polynomial-time (for example exponential time) lower bound.

2.

If a polynomial-time algorithm is discovered for even one NP-complete problem, then all NP-complete problems will be solvable in polynomial-time.

It is believed (but so far no proof is available) that NP-complete problems do not have polynomial-time algorithms and therefore are intractable. The basis for this belief is the second fact above, namely that if any single NP-complete problem can be solved in polynomial time, then every NP-complete problem has a polynomial-time algorithm. Given the wide range of NP-complete problems that have been discovered to date, it will be sensational if all of them could be solved in polynomial time.

It is important to know the rudiments of NP-completeness for anyone to design "sound" algorithms for problems. If one can establish a problem as NP-complete, there is strong reason to believe that it is intractable. We would then do better by trying to design a good approximation algorithm rather than searching endlessly seeking an exact solution. An example of this is the TSP (Traveling Salesman Problem), which has been shown to be intractable. A practical strategy to solve TSP therefore would be to design a good approximation algorithm. This is what we did in Chapter 8, where we used a variation of Kruskal's minimal spanning tree algorithm to approximately solve the TSP. Another important reason to have good familiarity with NP-completeness is many natural interesting and innocuous-looking problems that on the surface seem no harder than sorting or searching, are in fact NP-complete.