Complexity Theory
Introduction
This module covers advanced complexity theory.
Contents
The module includes the following topics:
- Deterministic, non-deterministic, probabilistic and parallel computational models
- Complexity classes; reductions
- Complexity of approximation problems
- Selection of advanced topics such as interactive proofs, derandomisation, circuit complexity, communication complexity, parametric complexity
- Properties of NP-complete sets, autoreducibility, polynomial time hierarchy
- complexity of probabilistic algorithms.
Learning Objectives
Students are able to analyse the correctness, security and complexity of processes. Students will be able to classify algorithmic problems according to their complexity. Students will be able to analyse the relationship between different complexity classes.
Examination Methods
- Either a 90-minute written exam.
- Or a 20-30 minute oral examination.
Lecture: Complexity Theory
SWS: 2 ECTS: 2
Exercise: Complexity Theory Exercise
SWS: 2 ECTS: 4
Module Competences
| ID | Description | Disciplines | Prerequisites | Evidence | Author | Source |
|---|---|---|---|---|---|---|
| formal_methods_1 | apply formal methods in system design and software engineering. | Computer Science | Basic knowledge of software engineering. | Submit application of formal methods for a given software system. | University of Potsdam | Link |
| formal_methods_2 | Analyse theoretical and practical problems in modelling and implementation using formal methods together with others. | Computer Science | Basic knowledge of formal methods. | Participate in self-regulated team exercises and presentations. | University of Potsdam | Link |