Survey Lecture: Martin Grohe: The Quest for a Logic Capturing PTIME

Thursday, April 20, 2023, 12:30pm

Location: Computer Science Center, Building E2, ground floor, B-IT room 5053.2.

Speaker: Martin Grohe

 

Abstract:

"Problems that are hard to describe are hard to solve and vice versa." This claim may seem naive or just wrong at first sight, but it is the underlying idea of a deep and fruitful connection between the descriptive complexity and the computational complexity of computational problems. Here descriptive complexity refers to the “language resources” required to express a problem in a formal language, or logic whereas computational complexity refers to the computational resources needed to solve the problem.

There are logical characterisations of many common complexity classes such as NP or PSPACE, but the question of whether there is a logical characterisation of the class PTIME of polynomial time solvable problems remains open. It was first asked by Chandra and Harel (1982) in the context of database theory, and later in a slightly different form by Gurevich (1988) in the context of finite model theory.

In this talk, I will review the question and speak about negative as well as positive results spanning the last 40 years.