Complexity theory is an important addition to the theory of algorithms. Its aim is to understand why certain computational problems are difficult and to classify them according to their difficulty. The best known and most important example is the theory of NP-completeness. The course is taught in English and especially covers topics from following list:
- Complexity classes, P vs. NP
- Reductions and completeness
- Space complexity
- Hierarchy theorems
- Relativization and oracle Turing machines
- Polynomial-time hierarchy
- Probabilistic complexity classes
After registering in PAUL for this course, you are enrolled (up to 24 hours later) to our PANDA course via which we organise everything. Especially, we provide material and make announcements only via this PANDA course. If the automatic enrollment does not work for you, please contact us.