↑ Return to Teaching

Computability and Computational Complexity 2017

Description: Computability is the area of computer science that investigates computation as its main subject of interest: what is computation, how can a computation be carried out, why some problems are impossible to solve by computers, why some problems are difficult to solve, what degrees of difficulty are there. This field that was virtually inexistent some 30 years ago, has expanded tremendously and it has become by now a central part of computer science.

Learning objectives: After passing the course the student will master the main computational complexity classes, their underlying models of computation, and relationships. The student will understand the concept of reductions and its role in classifying problems by their computational complexity. The student will be able to show using reductions that a problem is NP-complete. (S)he will be familiar with the concepts of randomised, approximation, and parallel algorithms and aware of the related complexity classes.

Content

  • Turing machines
  • Unsolvable problems
  • Complexity classes, big O notation
  • P and NP
  • NP-complete problems
  • Randomized computation
  • Parallel computation
  • PSPACE-completenes

Literature

  • Course book: Christos H. Papadimitriou, Computational complexity. Addison-Wesley, 1994.

Additional reading

  • O. Goldreich. Computational complexity: a conceptual perspective. Cambridge University Press, 2008
  • M. Sipser. Introduction to the theory of computation. PWS Pub co, 1996.
  • O. Goldreich. P, NP, and NP-completeness. Cambridge University Press, 2010.
  • D. Harel. Computers ltd. What they really can’t do. Oxford University Press, 2000.

Credits: 5 sp.

Components: 26-28h lectures, exercise sessions, final exam.

Time schedule: The course starts on September 5, 2017 and ends in October.

  • The lectures are given every week on Tuesdays 10.15-11.45 and Fridays 10.15-11.45 in room 115A, Agora.
  • The exercises are held on Tuesdays 13.30-15.00 in room 115A, Agora.
  • Exam dates: TBA.

Prerequisites: Formal languages and automata, Datastructures, Algorithms.

Lecturer: Mikhail Barash, Computer Science, Åbo Akademi University and Turku Centre for Computer Science.

Teaching assistant: Victor Popescu, Computer Science, Åbo Akademi University.