Theory of Computability and Complexity

This course provides parts of the theoretical background for computer science. The course includes formal languages, finite automata, Turing machines, computability, polynomical reduction, complexity classes and Cook's Theorem.

1. Knowledge. The student has mastered the most central formal methods for computations, formal languages, finite automata and Turing machines, and understands the concept of computability. The student has an overview of the most important complexity classes, such as P and NP, and has knowledge of NP-complete problems and Cook's theorem.

2. Skills. The student can do computations with formal languages, finite automata and Turing machines. Using polynomial reduction, the student is able to do computations and assessments concerning the complexity class of a given problem.

Lectures and exercises. The lectures may be given in English. If the course is taught in English, the exam will be given only in English. Retake of examination may be given as an oral examination.