#
Monday Lecture and Colloquium

**Monday, December 15, 2008 **

Humboldt-Universität Berlin

Institut für Informatik

Rudower Chaussee 25

Humboldt-Kabinett, 1st floor, between house III and IV

12489 Berlin

** Lecture - 14:15**

### Martin Grohe - HU Berlin

### The Quest for a Logic Capturing PTIME

*Abstract:*

Descriptive complexity is based on the paradigm that problems hard to solve
algorithmically are hard to describe formally and vice versa. This vague
paradigm is made precise in numerous results stating that logics characterize,
or c a p t u r e, complexity classes.

The central open problem in descriptive complexity theory is the question of
whether there exists a logic capturing PTIME. A good part of my talk will be
an introduction into the background of this question for non-experts (and
non-logicians). Then I will explain a recent result stating that fixed-point
logic with counting captures polynomial time on all classes of graphs with
excluded minors. A consequence of this result is that the Weisfeiler-Lehman
algorithm, a simple and generic combinatorial algorithm, can be used as a
polynomial time isomorphism test for graph classes with excluded minors.

**Colloquium - 16:00**

### Bastian Laubner - HU Berlin

### Rank Logics and Capturing Parity-L

*Abstract:*

Fixed-point logic with counting captures PTIME on many large classes of
graphs, as shown in Martin Grohe's preceding talk. However, it is not
expressive enough to capture PTIME on the class of all structures. For
example, it cannot be used to calculate the rank of a matrix over a
finite field, even though this is a classical polynomial time computation.

In my talk, I will introduce operators that decide the rank of logically
defined matrices. It will be explained that fixed-point logic together
with such rank operators is indeed more expressive than enhancing the
logic with just the ability to count. I will hint at some open problems
in a proof that such a rank logic captures or does not capture PTIME. In
the end, I will show that first-order logic with rank operators over the
two-element field captures the complexity class Parity-L in the presence
of a linear order.

Letzte Aktualisierung:
03.12.2008