A. Dawar's tutorial at the
Fall school (Sept.'11)

Descriptive Polynomial Time Complexity

In a paper in 1982, Chandra and Harel asked the question of whether there exists a logic that expresses exactly the polynomial-time computable properties of finite structures in the same way that Fagin had proved that existential second-order logic captures NP. This question remains open after nearly three decades and has been a central motor of work in descriptive complexity theory. In this tutorial, I will give a history of the problem and cover some highlights of results that have been obtained over the years. This will lead to a presentation of recent results examining the descriptive complexity of problems from linear algebra.

Lecture 1 will introduce the question posed by Chandra and Harel, place it in the context of Fagin's theorem. It will also explore the relationship between the existence of a logic for P and the existence of complete problems under logical reductions. This material is classical and can be found in standard textbooks on Finite Model Theory such as those by Ebbinghaus-Flum [1] and Libkin [2]

Lecture 2 will introduce fixed-point logics with counting and explore why they fail to capture P in general, though they do capture P on many interesting classes of structures. Useful references are the monograph by Otto [3] and the unpublished monograph by Grohe [4]

Lecture 3 will examine the definability of problems from linear algebra in fixed-point logic with counting and explain why these form an interesting frontier of definability. Useful references are the papers [5], [6], [7] and the thesis [8].

Lecture 4 will look at active research questions in the area. In particular, we will examine the definability of various problems surrounding solvability of equations over groups, rings and fields and reducibilities among them. Much of this is work in progress.

[1] H-D. Ebbinghaus and J. Flum. Finite Model Theory (2nd ed.). Springer 1999. url.

[2] L. Libkin. Elements of Finite Model Theory. Springer 2004. url.

[3] M. Otto. Bounded Variable Logics and Counting. Lecture Notes in Logic vol. 9. url.

[4] M. Grohe. Descriptive Complexity, Canonisation, and Definable Graph Structure Theory. url.

[5] A. Atserias, A. Bulatov, A. Dawar. Affine systems of equations and counting infinitary logic. Theor. Comput. Sci. 410:1666-1683 (2009) url.

[6] A. Dawar. On the Descriptive Complexity of Linear Algebra. WoLLIC 2008. Springer LNCS vol. 5110 url.

[7] A. Dawar, M. Grohe, B. Holm, B. Laubner. Logics with Rank Operators. LICS 2009. url.

[8] B. Holm. Descriptive Complexity of Linear Algebra. PhD Thesis, University of Cambridge 2010. url.