Chapter 6

NP-completeness

In this chapter, we introduce the complexity classes that are of paramount

importance for algorithm designers: P, NP, and NPC. We take a strictly prac-

tical approach and determinedly skip the detour through Turing machines. In

other words, we limit ourselves to NP-completeness, explaini ng it s i mportance

and detailing how to prove that a problem is NP-complete.

After introducing our approach in Section 6.1, we deﬁne the complexity

classes P and NP in Section 6.2. NP-complete problems are introduced in

Section 6.3, along with the practical reasoning to prove that a problem is

NP-complete. Several examples are provided in Section 6.4. We discuss sub-

tleties in problem deﬁnitions in Section 6.5 and strong NP-completeness in

Section 6.6. Finally, we make our conclusions in Section 6.7.

6.1 A practical approach to complexity theory

This chapter introduces the key complexity classes that algorithm designers

are confronted with: P, which stands for Polynomial, and NP, which stands

for Nondeterministic Polynomial. In fact, we depart from the original deﬁ-

nition of the class NP and use the (equivalent) characterization Polynomial

with Certiﬁcate. Within the NP class, we focus on the subclass NPC of NP-

complete problems.

When writing this chapter, we faced a cruel dilemma. Either we use a formal

approach, which requires an introduction to Turing machines, explain their

characteristics, and classify the languages that they can recognize, or we use

a practical approach that completely skips the detour through the theoretical

computer science framework and deﬁnes complexity classes out of nowhere

(almost!). We ﬁrmly believe that there is no trade-oﬀ in between, and that

a comprehensive exposure does require Turing machines. However, given the

main objectives of this book, we chose the latter approach. The price to pay

is that the reader will have to take for granted a key result, namely Cook’s

theorem [25], which we will state without pr oof. Cook’s theorem provides the

ﬁrst NP-complete problem, and we will have to trust him on this. However,

the main ad vantage is that we can concentrate on the art of the algorithm

125

© 2014 by Taylor & Francis Group, LLC

Start Free Trial

No credit card required