## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

No credit card required

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

## With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

No credit card required