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

Get Theory of Computational Complexity, 2nd Edition now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.