Introduit la complexité computationnelle, les problèmes de décision, la complexité quantique et les algorithmes probabilistes, y compris les problèmes dures au NP et les problèmes complets au NP.
Examine les problèmes de NP, la coloration des graphiques, l'optimisation des chemins et les distinctions de complexité computationnelle dans les classes P et NP.
