Nach positiver Absolvierung der Lehrveranstaltung sind Studierende in der Lage......
As this course is given in English, please ignore above introductory words.
After successful completion of the course students will 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.
Literatur: 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.
Nicht erforderlich
Grundlagen der Logik oder der allgemeinen Algebra.
