Algorithm Theory
VU 3 SS 2007 LVA 703608
Description
The lecture is an introduction to the theory of computational complexity.
Content
| Week 1: | Introduction, Problems and Algorithms. |
| Week 2: | Turing machines as algorithms, multiple-string TMs. |
| Week 3: | Random access machines, nondeterministic machines. |
| Week 4: | Complextiy classes, The Hierarchy Theorem |
| Week 5: | The reachability method, Savitch's Theorem. |
| Week 6: | Reductions, completeness, Cook's Theorem |
| Week 7: | Logical characterizations, Fagin's Theorem |
| Week 8: | NP-complete problems, Variants of SAT |
| Week 9: | Graph-theoretical problems, Sets and numbers |
| Week 10: | coNP, Pratt's Theorem |
| Week 11: | Function problems |
| Week 12: | Randomised Computation |
| Week 13: | Cryptography |
| Week 14: | Approximations |
Literature
The lecture is based on the following book:Papadimitriou, "Computational Complexity"Note that you can obtain the book at a reduced fee through the link. The book is also available in the "Semesterapparat" at the library.
Addison-Wesley, 1994.
For complementary reading we propose:
Michael Sipser, "Introduction to the Theory of Computation"The book is available in the library (signature N18743, classification I3-SIP). A few of the definitions and proofs in the slides are taken from this book.
PWS Publishing Company, 1997