Teaching
Contents
Computational complexity theory aims to classify computational problems according to the algorithmic resources required for their solution. Resources are for example time, space, nondeterminism, or randomness. A central role is played by the class P of problems solvable in polynomial time. The central problem is the P versus NP problem, one of the Clay institute's millenium problems of mathematics, and, according to Smale, one of the three greatest open problems of mathematics. The course offers an introduction to this problem and its surrounding theory.
Lectures
Tuesday and Thursday 10:00-12:00 in SR030 (IM)
Exercises
By Azza Gaysin Thursday 14:00-16:00 and 16:00-18:00 in SR007 (IM)
New exercise sheet every Tuesday afternoon on StudIP
Literature
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
Contents
Model theory = Algebra + Logic
The copurse offers an introduction into classical model theory. Special emphasis is given on examples and applications, especially in algebra.
I Ordinals and cardinals
II Boolean algebras and ultraproducts
III Back and Forth
IV Diagrams
V Types
VI Quantifier elimination
VII Countable structures
Regularly updated lecture notes on StudIP.
Lectures
Tuesday 12:00-14:00 in HS11 (IM)
Thursday 12:00-14:00 in HS12 (IM)
Exercises
By Azza Gayin Wednesday 16:00-18:00 in HS12 (IM)
New exercise sheet Tuesday afternoon on StudIP.
Literature
Chang, Keisler, Model theory, 3rd edition, North Holland, 1990.
Tent, Ziegler, A Course in Model Theory (Lecture Notes in Logic), Cambridge University Press, 2012.
Marker, Model Theory : An Introduction, Springer Graduate Texts in Mathematics 217, 2010. Here.
This is an advanced seminar joint with the chair of Pure Mathematics. Advanced students who wish to deepen their knowledge in mathematical logic and/or complexity theory can give talks on jointly chosen and jointly elaborated topics.
Share this page
