[ INBIPVOBEKO ] VL Computability and Complexity

(*) Unfortunately this information is not available in english.
Workload Education level Study areas Responsible person Hours per week Coordinating university
3 ECTS B2 - Bachelor's programme 2. year Computer Science Richard Küng 2 hpw Johannes Kepler University Linz
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:

  1. finite state automata
  2. Turing machines
  3. uncomputable functions & the Halting Problem
  4. the problem class P ("problems that are easy to solve")
  5. the problem class NP ("problems whose solution can be easily checked")
  6. reductions and NP-completeness
  7. SAT (satisfiability) & the Cook-Levin Theorem
  8. coNP and the polynomial hierarchy
  9. factoring, discrete logarithm & graph isomorphism ("important problems where we don't know if they are actually hard")
  10. 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)
On-site course
Maximum number of participants -
Assignment procedure Direct assignment