# Complexity Theory (CxT)

- Dr. Dieter Probst

- Dr. Michel Marti

- Tuesday from 14:15 to 17:00

### Description:

In this course we will give a thorough and self-contained introduction to the area of computational complexity theory. Starting off from the abstract computational model of a Turing machine, we will discuss deterministic and non-deterministic time- and space complexity classes with regard to their structural and algorithmic properties. We will address numerous relevant examples while putting some emphasis on the complexity classes P and NP as well as to the theory of NP-completeness. Some keywords: dynamic complexity measures; deterministic and nondeterministic polynomial time; the P versus NP problem and its relativization, NP completeness; the polynomial hierarchy and PSPACE.

On successful completion of this course, you will be able to:

- Classify algorithmic problems into complexity classes
- Determine the known relationships between complexity classes
- Show that an algorithmic problem in NP-complete
- Understand the P versus NP problem
- Discuss problems whose complexity is beyond NP
- Understand problems with polynomial space complexity

### References:

To be announced.