Le verbe « relativiser » a été rendu pronominal : « se relativiser » pour rendre le « to relativise » anglais (introduction et chapitres 7 et 10).
Définition 1-M (simulation), page 15 : le morphisme de sortie doit préserver les longueurs pour être inversible facilement.
Démonstration du théorème de Cook et Levin 3-V, page 73 : si le calcul N(x) prend moins de t(n) étapes, il faut rester dans le même état jusqu'au temps t(n).
Proposition 4-J (composition de fonction calculables en espace), page 101 : la composition se calcule en espace O(s_g(|x|)+s_f(|g(x)|)), et non O(s(|x|)+log(|g(x)|)). La démonstration a été corrigée.
Lemme 8-T, page 208 : il faut préciser qu'un seul appel à l'oracle est effectué sur chaque chemin de calcul. C'est nécessaire pour la démonstration du théorème 8-S, modifiée en conséquence (p. 210).
Définition 9-Q (réduction de comptage), page 217 : s doit aussi prendre x en entrée. C'est nécessaire pour la complétude du permanent (démonstrations p. 243 du lemme 9-AS, et p. 245 du lemme 9-AT, corrigées en conséquence).
Démonstration du lemme 9-AN, page 234 : la fonction 4x^3+3x^4 fait passer d'un modulo 2^i à un modulo 2^{2i} (et non 2^{i+1}).
Complétude du permanent (section 9.5.2), page 240 : dans les gadgets de littéral, les arcs utilisés plusieurs fois doivent être scindés. La figure 9.5 page 242 a été modifiée en conséquence.
Démonstration du théorème de Razborov et Smolensky (11-T), page 301 : MOD_{i,p} est obtenu à partir de MOD_p en passant i uns en zéros, et non l'inverse.
Énoncé du lemme 12-AI, page 336 : l'argument pour l'unicité de p est modifié.
Exercice B-B, page 363 : remplacer EXPSPACE par DSPACE(2^{O(n)}) et EXP par E. La correction page 384 a été modifiée en conséquence.