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.
Continuously updated lecture notes on StudIP.
Lectures
Tuesday 12:00-14:00 IM SR030
Wednesday 10:00-12:00 JUR HS12
Exercises by Johannes Heil
Thursday 10:00-12:00 JUR SR 154
Literature
Arora, Barak, Computational Complexity: A Modern Approach, Cambridge University Press, 2009. Draft
Papadimitriou, Computational Complexity, Addison-Wesley, 1995.
This is an advanced seminar joint with Tobias Kaiser. It offers research talks of the respective groups and their visitors. 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.
Program TBA
Model theory = logic + algebra
The course offers an introduction to classical model theory. It develops a broad general toolkit to construct and analyze theories and their models. It gives special emphasis to applications and examples, especially from algebra. It starts with a crash course in set theory and infinite cardinal numbers, and continues with the theory of Boolean algebras, ultraproducts, the back and forth method, algebraic and elementary diagrams, realizing and omitting types, quantifier elimination, applications thereof to algebraically closed and real closed fields, and finally describes theories with exactly one countable model (up to isomorphism).
Literatur
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.
The course continues the one from last semester with group theory and field theory.
On StudIP you find regularly updated lecture notes.
Lectures
Tuesday and Thursday 10:00-12:00 (JUR) SR 059
Exercises by Daniel Yoon
Monday 10:00-12:00 (WIWI) SR 027
Literature
M. Artin, Algebra, Pearson, 2013 here
G. Fischer, Lehrbuch der Algebra, 2017 here
S. Bosch, Algebra, Springer, 2023 here
