June 2014
Intermediate to advanced
512 pages
17h 55m
English
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.
The complexity class NP has a nice characterization in terms of class P and polynomial length-bounded existential quantifiers.