Cette page recense les corrections réalisées sur
la version en ligne de mon livre Complexité
algorithmique, par rapport à
la version
imprimée par les éditions Ellipses. Merci aux lecteurs attentifs qui
m'ont signalé une grande partie de ces erreurs.
- 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.