Next:10.6
To Probe FurtherUp:10.5
NPComplete ProblemsPrevious:10.5
NPComplete Problems
10.5.1 NPHardness and NPCompleteness
A decision problem Y is said to be NPhard if X
Y
X
NP. An NPhard problem Y is said to be NPcomplete if Y
NP.
NPC is the standard notation for the class of all NPcomplete problems.

Informally, an NPhard problem is a problem that is at least as hard as
any problem in NP. If, further, the problem also belongs to NP,
it would become NPcomplete.

It can be easily proved that if any NPcomplete problem is in P,
then NP = P. Similarly, if any problem in NP is not
polynomialtime solvable, then no NPcomplete problem will be polynomialtime
solvable. Thus NPcompleteness is at the crux of deciding whether or not
NP = P.

Using the above definition of NPcompleteness to show that a given decision
problem, say Y, is NPcomplete will call for proving polynomial reducibility
of each problem in NP to the problem Y. This is impractical since
the class NP already has a large number of member problems and will
continuously grow as researchers discover new members of NP.

A more practical way of proving NPcompleteness of a decision problem
Y is to discover a problem X NPC
such that X
Y. Since X is NPcomplete and
is a transitive relationship, the above would mean that Z
Y
Z NP.
Furthermore if Y NP,
then Y is NPcomplete.
The above is the standard technique used for showing the NPhardness
or NPcompleteness of a given decision problem. For example, all the decision
problems given in Section 10.2 can be shown to be NPcomplete by the above
technique.

An interesting question is: how was the first member of NPC found?
Stephen Cook showed the NPcompleteness of the problem 3SAT by directly
proving that X
3SAT
X NP.

If a problem is NPcomplete, it does not mean that all hopes are lost.
If the actual input sizes are small, an algorithm with, say, exponential
running time may be acceptable. On the other hand, it may still be possible
to obtain nearoptimal solutions in polynomialtime. Such an algorithm
that returns nearoptimal solutions (in polynomial time) is called an approximation
algorithm. Using Kruskal's algorithm to obtain a suboptimal solution to
the TSP (see Chapter 8) is an example of this.
Next:10.6
To Probe FurtherUp:10.5
NPComplete ProblemsPrevious:10.5
NPComplete Problems
eEL,CSA_Dept,IISc,Bangalore