O'Reilly logo

A Guide to Algorithm Design by Frédéric Vivien, Yves Robert, Anne Benoit

Stay ahead with the world's most comprehensive technology and business learning platform.

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

Start Free Trial

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 define 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 definitions 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 defi-
nition of the class NP and use the (equivalent) characterization Polynomial
with Certificate. 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 defines complexity classes out of nowhere
(almost!). We firmly believe that there is no trade-off 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
first 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.

Start Free Trial

No credit card required