| Detailed information |
| Original study plan |
Bachelor's programme Computer Science 2021W |
| Objectives |
Computers have been developed to, well, compute things. But not all computational tasks are equally difficult. Some are easy (e.g. multiplying two large prime numbers), while others appear to be much harder (e.g. factorizing a product of two large prime numbers). In this introductory course for theoretical computer science, the students learn how to appropriately formalize questions about computability (can we actually compute "something"?) and computational complexity (how hard is it to compute "something"?). A firm grasp of these concepts will allow students to gauge whether a given computational task is easy, or likely to be prohibitively challenging. Finally, we will also discuss the potential impact of quantum computers on the landscape of (classical) complexity theory.
|
| Subject |
Topics to be covered:
- finite state automata
- Turing machines
- uncomputable functions & the Halting Problem
- the problem class P ("problems that are easy to solve")
- the problem class NP ("problems whose solution can be easily checked")
- reductions and NP-completeness
- SAT (satisfiability) & the Cook-Levin Theorem
- coNP and the polynomial hierarchy
- factoring, discrete logarithm & graph isomorphism ("important problems where we don't know if they are actually hard")
- quantum computers as potential game changers
|
| Criteria for evaluation |
Written exam
|
| Methods |
Blackboard presentation
|
| Language |
(*)Deutsch; English for written documents |
| Study material |
S. Arora and B. Barak, Computational Complexity: A Modern Approach
|
| Changing subject? |
No |
| Further information |
tba
|
| Corresponding lecture |
(*)INBPCVOFOG2: VO Formale Grundlagen 2 (3 ECTS)
|
