|18 February:||introduction and computational complexity of FO|
|27 February:||Fagin’s theorem|
|6 March:||Fixed Point Logics: IFP, TCL|
|13 March:||Ehrenfeucht-Fraisse games [Chapter 3 from Libkin’s book]|
|20 March:||0-1 laws [Chapter 12, Sections 1-3 from Libkin’s book]|
|27 March:||Partial Fixed Point logic and the Abiteboul-Vianu theorem|
|3 April, 10 April:||Gaifman and Hanf locality [Chapter 2, Sections 4,5 from the Ebbinghaus-Flum book]|
|17 April:||Easter break|
|25 April:||logics for PTime and the CFI construction|
|1 May:||spring break|
|8 May:||Logics for Ptime, canonisation and isomorphism|
|15 May:||Conjunctive Queries – [see also chapter 5 from these lecture notes for the Theory of Databases]|
|22 May:||Constraint Satisfaction Problems – basics and basics of the algebraic approach [see also chapters 1,2 from this exposition by Manuel Bodirsky]|
|29 May, 5 June:||Computing with Acyclic Joins [chapter 6 from these lecture notes for the Theory of Databases]|
In this post, we continue the study of the complexity of Constraint Satisfaction Problems (see previous post). We introduce an algebraic tool for this, namely, polymorphisms.
Poniżej jest lista tematów egzaminacyjnych obowiązująca na egzaminie ustnym z Teorii Modeli Skończonych.
We discuss the basics of Constraint Satisfaction Problems (CSPs). Some basic facts concerning the algebraic approach to CSPs are presented in the next post.
This post discusses some basic facts about conjunctive queries, the containment problem, and minimization.
In this post, we consider the question of the existence of a logic corresponding to PTime more formally, and we relate it to the graph isomorphism problem. This post is loosely based on a chapter of Martin Grohe’s book.
Recall the following result from this post.
Theorem (Immerman-Vardi). Over linearly-ordered, finite structures, IFP is equally expressive as PTime.
In this post we will prove the theorem of Cai, Fürer and Immerman that the above result does not extend to the class of all finite structures. Using a geometric argument, we show that the logic IFP+C cannot determine solvability of systems of linear equations modulo $2$.
In the meantime, we studied Ehrenfeucht-Fraisse games, finite variable logic, k-pebble games and 0-1 laws. The relevant material is in Libkin’s book, in chapters 3, 11.1, 11.2 and 12.
Now we come back to the study of logics capturing known complexity classes.
In view of Fagin’s Theorem, a the following question arises.
The big question. Does there exist a logic $\Ll$ such that a property of finite structures is definable in the logic $\Ll$ if and only if it is in PTime?
We will see that fixpoint logic offers a partial answer to this question.
We will see one of the first results relating precisely the expressive power of a logic with a complexity class.