Při zkoušce požaduji znalosti v rozsahu první části knihy:

 

S. Arora and B. Barak, Computational Complexity, A Modern Approach.

 

t.j., prvních 11 kapitol. (Jedna verze knihy je volně na internetu.) Po dohodě je možno jednu kapitolu vynechat. Doporučuji také využít možnost vyměnit některé kapitoly z první časti knihy za kapitoly z dalších částí knihy. Takto se můžete naučit něco, co jste neměli v základním kurzu. Tato kniha není ideální na učení, proto doporučuji se podívat do poznámek z přednášek, nebo použít další literaturu:

 

O. Goldreich, Computational Complexity: A Conceptual Perspective

 

C. Papadimitrou: Computational Complexity

 

Doporučuji, abyste přišli alespoň jednou na konzultaci, abych mohl otestovat vaše znalosti a vy jste se mohli vyvarovat potížím při zkoušce.