department
wg bkb
Complexity
A course by Lutz Schröder at the Universität Bremen 2005.
The theory of complexity is concerned with the question of what resources (time, storage space etc.) are required in order to solve a given computational problem. There is a hierarchy of so-called complexity classes, which includes e.g. the classes P of problems solvable by deterministic algorithms in polynomial time, and NP of problems solvable by non-deterministic algorithms in polynomial time. It is a long-standing and fascinating open problem to determine whether or not P=NP. You're only in it for the money? Then this is the course for you: proving or disproving P=NP is the only chance for you as a computer scientist to earn the fabled Clay prize worth 1.000.000 US dollars. The course will be based on the bookNeil D. Jones: Computability and Complexity from a Programming Perspective, MIT Press, 1997
Further literature:- John E. Hopcroft, Rajeev Motwani, and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison-Wesley, 2001
- Christos H. Papadimitriou, Computational Complexity, Addison Wesley, 1994
Course Material
- Slides on the definition of recursive and recursively enumerable sets
- Slides on the WHILE self-interpreter
- Slides on characterizations of recursive and r.e. sets
- Problem Sheet 1
- Slides on Turing Machines
- Slides on DAGs
- Problem Sheet 2
- Slides on space versus time
- Slides on nondeterminism
- Slides on graph path search
- Slides on graph inaccessibility
- Problem Sheet 3
- Slides on state graphs
Author: Dr. Lutz Schröder
| Last updated: June 16, 2005 |  |