O'Reilly logo

Design and analysis of Algorithms, 2nd Edition by Himanshu B 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

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

RAM /abr./: Rarely Adequate Memory.

—Anonymous

A grain of wisdom is worth an ounce of knowledge, which is worth a ton of data.

—Neil Larson

Chapter Outline

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