After successful completion of the course, students are able to have a basic understanding of interactions of mathematical logic with computational complexity. They will unterstand the fundamentals of computation, be able to formalize computation and translate logical descriptions of computational problems into algorithms and vice-versa.
A logical description of the complexity class NP, some (un-)definability resutls for finite structures, Gödel's incompleteness theorem and the undecidability of the halting problem for Turing machines.
The subject is presented on the blackboard.
Literature: L. Libkin, Elements of finite model theory
http://homepages.inf.ed.ac.uk/libkin/fmt/fmt.pdf
An oral exam is held at the end of the semester.
Not necessary
Basic knowledge of mathematical logic or of general algebra.