10.1 Importance of NP-Completeness (2024)

(1)

Although a problem which has a running time of sayO(n²⁰)orO(n¹⁰⁰) canbe called intractable, there are very few practical problems with suchorders of polynomial complexity.

(2)

For reasonable models of computation, a problem that can be solved in polynomialtime 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.)

1.

No polynomial-time algorithm has yet been discovered for any NP-completeproblem; at the same time no NP-complete problem has been shown to havea 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 important to know the rudiments of NP-completeness for anyoneto design "sound" algorithms for problems. If one can establish a problemas NP-complete, there is strong reason to believe that it is intractable.We would then do better by trying to design a good approximation algorithmrather than searching endlessly seeking an exact solution. An example ofthis is the TSP (Traveling Salesman Problem), which has been shown to beintractable. A practical strategy to solve TSP therefore would be to designa good approximation algorithm. This is what we did in Chapter 8, wherewe used a variation of Kruskal's minimal spanning tree algorithm to approximatelysolve the TSP. Another important reason to have good familiarity with NP-completenessis many natural interesting and innocuous-looking problems that on thesurface seem no harder than sorting or searching, are in fact NP-complete.