ICE-TCS Lectures Series - Bjarki Holm - Finding a Logical Characterisation of Polynomial Time

The next ICE-TCS  talk for this semester will be delivered on Friday, 13 November, by Bjarki Holm (University of Cambridge, UK). The talk, which is entitled Finding a Logical Characterisation of Polynomial Time, will be held at 14:00-15.00 in room K5 at Reykjavik University (Kringlan 1). 

Further information about forthcoming ICE- TCS events may be found at the news page

Abstract

Descriptive complexity theory studies the relationship between logic and computational complexity. One of the main open questions in this area is whether there exists a logic that can express exactly all the polynomial-time computable (PTIME) properties of finite structures. One reason why this question is interesting is that we know from a result of Fagin that the class NP is captured by the existential fragment of second-order logic. Finding a logic for PTIME would therefore allow logical (in particular, model-theoretic) techniques to be applied to one of the most important questions of computational complexity, that whether PTIME = NP. 

Over the past three decades, there have been a number of attempts to define a logic for PTIME, mainly by considering extensions of first-order and fixed-point logics. We show that all the known shortcomings of previously proposed logics relate to their inability to determine the solvability of systems of linear equations; or more generally, their inability to define the rank of a matrix. This leads us to consider extensions of first-order and fixed-point logics with operators for computing the matrix rank of definable relations. We show that fixed-point logic with rank can define the various polynomial-time problems that previously resisted logical classification and it is an open question whether it can capture all of PTIME. We also consider the expressive power of first-order logic with rank and show that in the presence of a linear order this logic captures the complexity class Parity-L, whose descriptive complexity had been previously unknown.

This is joint work with Anuj Dawar (University of Cambridge), Martin Grohe (Humboldt University, Berlin) and Bastian Laubner (Humboldt University, Berlin).