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

Na Internetu můžete najít i videa z přednášek, například toto.