Home | deutsch  | Legals | Sitemap | KIT

Computational Complexity II

Computational Complexity II
type: lecture
chair: Fakultät für Informatik
semester: summer semester 2010
place:

seminar room 301 (50.34)

time:

Thu 11:30-13:00 (every two weeks)

start: 22.04.2010
lecturer:

Olga Tveretina,Carsten Sinz

sws: 1
lv-no.: 24661

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.