Next:10.5.1
NP-Hardness and NP-CompletenessUp:10.
Introduction to NP-CompletenessPrevious:10.4
The Classes P and NP
10.5 NP-Complete Problems
The definition of NP-completeness is based on reducibility of problems.
Suppose we wish to solve a problem X and we already have an algorithm for
solving another problem Y. Suppose we have a function T that takes an input
x for X and produces T(x), an input for Y such that the correct answer
for X on x is yes if and only if the correct answer for Y on T(x) is yes.
Then by composing T and the algorithm for y, we have an algorithm for X.
eEL,CSA_Dept,IISc,Bangalore