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 October 26, 2015 and ends mid-December.
- The lectures are given every week on Mondays 10.15-11.45 and Wednesdays 10.15-11.45 in room Catbert B3028, ICT House.
- The exercises are held on Mondays 13.30-15.00 in room Catebert B3028, ICT House.
- Exam dates: December 18, 2015 and January 8, 2016.
Prerequisites: Formal languages and automata, Datastructures, Algorithms.
Registration (also for the exam): Through MinPlan.
Lecturer: Ion Petre, Computer Science, Abo Akademi University.
Links:
- Lecture notes
- Lecture 1: Problems and algorithms
- Lecture 2: Turing machines
- Lecture 3: Linear speed-up; Space complexity; Nondeterministic complexity
- Lecture 4: Universal Turing machines. Undecidability
- Lecture 5: Boolean logic
- Lecture 6: Relations between complexity classes
- Lecture 7: Relations and completeness
- Lecture 8: NP-complete problems (I)
- Lecture 9: NP-complete problems (II)
- Lecture 10: Randomized computation
- Lecture 11: Approximability
- Lecture 12: On P vs NP
- Lecture 13: Summary of the course
ยท Exercises
Last updated: September 5, 2018.