Recommended literature:

• Christos Papadimitriou, Computational Complexity, Addison-Wesley, 1993.
  Wydanie polskie: Zlozonosc obliczeniowa, WNT 2002.
• Dexter Kozen, Theory of Computation, Springer, 2006.
• Michael Soltys, An Introduction to Computational Complexity, Wydawnictwo Uniwersytetu Jagiellonskiego, 2009.
• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009 (draft).
• Oded Goldreich, P, NP, and NP-Completeness. The Basics of Complexity Theory, Cambridge University Press, 2010 (draft).