The book covers recent developments in complexity theory, the probabilistic approach and its links with crypto, quantum computation and the famous theorem perfectly husked PCP, among others. He takes over from the classic "A Guide to the Theory of NP-Completeness" by Garey and Johnson. Concepts are clearly identified and the book is very educational. Attention, it is not a popular work, the concept of proof being central, reading requires some mathematics in culture (discrete in particular) and is intended primarily for theoretical computer science or mathematics students (after the license) and of course to all the scientists who want to approach this theory.