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 NPcompleteness
 SAT (satisfiability) & the CookLevin 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)
