Computational Complexity theory looks at the computational resources  needed to solve computational problems, and it is especially concerned with the distinction between "tractable" problems, that we can solve with reasonable amount of resources, and "intractable" problems, that are beyond the power of existing computers.

We will focus, among others, on the following topics:

• Examples of NP-complete problems: the Hamiltonian path problem, the SUBSET-SUM problem
• Complexity of counting: the class #P, #P completeness and examples of problems in #P
• Randomized computing: the class BPP, randomized reductions
• Quantum computing: quantum circuits, quantum algorithms.

Prerequisites for this course: familiarity with concepts such as Turing machine, NP-completeness, NP-hardness.

Recommended textbooks:

• Christos H. Papadimitriou. Computational Complexity
• Sanjeev Arora and Boaz Barak. Complexity Theory: A Modern Approach
• Michael Sipser. Introduction to the Theory of Computation
• Oded Goldreich. Computational Complexity: A Conceptual Perspective.

Further information is available at http://baldur.iti.uka.de/~olga/Site/Teaching.html.