O'Reilly logo

Theory of Computational Complexity, 2nd Edition by Ker-I Ko, Ding-Zhu Du

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 2

NP-Completeness

Nor has there been agreement about the right road to truth.

—Isaiah Berlin

The notions of reducibility and completeness play an important role in the classification of the complexity of problems from diverse areas of applications. In this chapter, we formally define two types of reducibilities: the polynomial-time many-one reducibility and the polynomial-time Turing reducibility. Then we prove several basic NP-complete problems and discuss the complexity of some combinatorial optimization problems.

2.1 NP

The complexity class NP has a nice characterization in terms of class P and polynomial length-bounded existential quantifiers.

Theorem 2.1

Proof

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