**1st day (2009-07-13) - Introduction to Computability Theory**
- Math preliminaries, Problems as languages, Landau Symbols
- Turing machines, decidability, non-determinism
- Turing reductions, halting problem
**2nd day (2009-07-14) - Complexity classes**
- Time and space complexity
- Reductions, hardness, completeness
- Non-determinism
**3rd day (2009-07-15) - Polynomial Complexity**
- Inside P
- NP, NP-complete
- SAT, NodeCover, Clique, KnapSack, MultiprocessorScheduling, ...
**4th day (2009-07-16) - The P-vs-NP Problem**
- The problems GI and PRIMES
- Oracles, Polynomial time hierarchy
- Relativization
**5th day (2009-07-17) - Other complexity concepts**
- Non-uniform complexity: Circuits
- Interactive Proof Systems
- Probabilistic complexity classes
In the end of every day, the students will be given a couple of small problems to solve, for deepening the understanding of the day's lectures. |