Introduction to Complexity Theory: Understanding of basic notions, concepts, methods, and results.

Basic notions of complexity theory, deterministic und non-deterministic complextiy classes, NP-complete problems, logarithmic space, the polynomal hierarchy, exponentially hard probleme, applications. Didactical Concept: *) The contents is presented by the course instructor. *) Interaction: The students are asked questions to stimulate the ability to think for themselves. On the other hand, students are encouraged to contribute to the lecture by questions/comments. *) Homework assignments allow the students to practice the methods taught in the lecture (in particular, "clean" mathematical proofs of complexity results). *) Reading assignments allow the students to read themselves more on related/advanced topics. Assessment: is based on homework/reading assignments as well as a written exam.

registration via TISS

aktuelle Infos bitte LVA abonnieren Ort: TISS

*) Students are assumed to have a basic knowledge in mathematical logic and to be familiar with basic concepts of complexity theory (to the extent taught in the course "Formale Methoden der Informatik"). *) Moreover, students should have basic mathematical skills (like carrying out proofs by induction) as taught in the mathematics courses in the bachelor studies.