Při zkoušce požaduji znalosti v rozsahu první kapitoly 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. 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