Computational Complexity

Contents of the course

What computing resources do we need to solve a computational problem? The computational complexity theory studies this question from a structural point of view. Building up on the Turing machine model, we will discover and study deterministic and nondeterministic complexity classes, space and time complexity and hierarchy, completeness, randomized algorithms classes, boolean circuits and counting classes.

 

Bibliography:

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak (mostly chapters 1 to 7)

more about computational complexity

 

De quelles ressources avons nous besoins pour résoudre un problème, faire un calcul ? La théorie de la complexité algorithmique étudie ce problème d’un point de vue structurel. En nous appuyant sur le modèle des machines de Turing, nous étudierons les classes de complexité déterministes et non déterministes, en temps et en espace, les hiérarchies entre ces classes, les problèmes complets, les algorithmes et classes probabilistes, les classes définies par les circuits ainsi que quelques notions sur les classes de comptage.

 

Bibliographie :

Computational Complexity: A Modern Approach, Sanjeev Arora and Boaz Barak, principalement les chapitres 1 à 7

Pour en savoir plus sur la théorie de la complexité algorithmique

https://fr.wikipedia.org/wiki/Théorie_de_la_complexité_(informatique_théorique)

Page du cours (for 2013-2014)

Teaching personnel