Theory of Computational Complexity, 2nd Edition

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

A language A is in NP if and only if there exist a language B in P, and a polynomial function p, such that for each instance x,

2.1

Proof

Let where is a one-tape NTM with a polynomial-time bound p(n). Similar to Theorem 1.9, we regard Δ as a multivalued function from to , and let k be the maximum number ...