Théorie de la complexité

Qu'est-ce que la théorie de la complexité ? Elle étudie le temps, la mémoire et les ressources nécessaires pour résoudre des problèmes algorithmiques, révélant ce que les ordinateurs peuvent accomplir et ce qui reste fondamentalement inaccessible même avec les meilleurs algorithmes. De P et NP aux réductions, NP-complétude, problèmes d'approximation, systèmes interactifs, PCP et complexité de communication, ce livre introduit pas à pas les concepts clés de l'informatique théorique.
Lucien Sina explique la théorie, transmet idées et intuitions, et propose de nombreux exemples et exercices avec solutions pour maîtriser les limites du calcul efficace.