O'Reilly logo

Design and Analysis of Algorithms by Himanshu B. Dave, Parag H. Dave

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 Introduction

18.1.1 NP-Hardness

18.1.2 NP-Completeness

18.1.3 Consequences of being in P

18.1.4 Reduction Source Problems

18.2 Turing Machine (TM)

18.2.1 Relation between Problems and Languages

18.2.2 Decision Problems and Languages

18.3 Reductions

18.3.1 Definition of Reductions

18.3.2 Reduction ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required