Chapter 18
Some NP and NP-Complete Problems
Objectives
After reading this chapter, you should understand:
- A few important Real Life NP-Hard and NP-Complete Problems in detail
- An Informal definition of NP-Hardness and NP-Completeness
- P and NP classes in terms of the Turing Machine
- Reducibility of problems so that NP Completeness can be proven
- How to use the notion of reducibility to prove NP-Completeness for several Classical Problems
Chapter Outline
18.1.3 Consequences of being in P
18.1.4 Reduction Source Problems
18.2.1 Relation between Problems and Languages
18.2.2 Decision Problems and Languages
Get Design and Analysis of Algorithms now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
