Théorie de la complexité

Qu'est-ce que la théorie de la complexité – et pourquoi est-elle si centrale en informatique ? La théorie de la complexité étudie combien de temps, d'espace mémoire ou d'autres ressources sont nécessaires pour résoudre des problèmes algorithmiques. Elle constitue le fondement pour comprendre ce que les ordinateurs peuvent accomplir – et ce qui reste, même avec les meilleurs algorithmes, fondamentalement inaccessible.

De classes classiques comme P et NP, en passant par les réductions, la comp...