Next:10.2
Optimization Problems and Decision ProblemsUp:10.
Introduction to NPCompletenessPrevious:10.
Introduction to NPCompleteness
10.1 Importance of NPCompleteness
Most algorithms we have studied so far have polynomialtime running times.
According to Cormen, Leiserson, and Rivest, polynomialtime algorithms
can be considered tractable for the following reasons.

(1)

Although a problem which has a running time of say
O(n^{20})
or O(n^{100}) 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 polynomialtime solvable problems has nice closure properties
(since polynomials are closed under addition, multiplication, etc.)
The class of NPcomplete (Nondeterministic 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 polynomialtime algorithm has yet been discovered for any NPcomplete
problem; at the same time no NPcomplete problem has been shown to have
a super polynomialtime (for example exponential time) lower bound.

2.

If a polynomialtime algorithm is discovered for even one NPcomplete problem,
then all NPcomplete problems will be solvable in polynomialtime.
It is believed (but so far no proof is available) that NPcomplete problems
do not have polynomialtime algorithms and therefore are intractable. The
basis for this belief is the second fact above, namely that if any single
NPcomplete problem can be solved in polynomial time, then every NPcomplete
problem has a polynomialtime algorithm. Given the wide range of NPcomplete
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 NPcompleteness for anyone
to design "sound" algorithms for problems. If one can establish a problem
as NPcomplete, 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 NPcompleteness
is many natural interesting and innocuouslooking problems that on the
surface seem no harder than sorting or searching, are in fact NPcomplete.
Next:10.2
Optimization Problems and Decision ProblemsUp:10.
Introduction to NPCompletenessPrevious:10.
Introduction to NPCompleteness
eEL,CSA_Dept,IISc,Bangalore