Where academic tradition
meets the exciting future

Computability and Computational Complexity (2017 Autumn)

Organisation: ÅAU / Faculty of Science and Engineering

Credit Points: 5

Responsible Person: Ion Petre, Mikhail Barash

Course code: 456508.0

After completing the course, the student is able to reason about computability and computational complexity of different kinds of problems.

Computability is the area of computer science that studies the notion of computation: which problems can be solved by computers, which problems cannot be solved (by any future computer technology), and even different ways of doing computations. Computational complexity is the aim of computer science that focuses on classifying computational problems according to their inherent difficulty: which problems are easy and which are difficult, and how difficult computational problems can be. Contents: Turing machines Unsolvable problems Complexity classes P and NP NP-complete problems Space Complexity Beyond Turing



  1. Tue 5.9.–24.10. weekly at 10–12 and 13–15, 115A
  2. Fri 7.9.–26.10. weekly at 10–12, 115A