Design and Analysis of Algorithms20785 marksNP Complete Problems, NP Completeness and Reducibility, Cook
Write short notes on: a. NP Hard Problems and NP Completeness b. Problem Reduction
Write short notes on: a. NP Hard Problems and NP Completeness b. Problem Reduction [5]
--- A problem is called NP-Complete if it satisfies two conditions: 1. It belongs to the class NP (the solution can be verified in polynomial time). 2. Every other problem in NP can be reduced to it in polynomial time (it is NP-Hard). NP-Complete problems are the hardest problems in NP. If any si...