The central open problem in descriptive complexity theory is the question
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 such graph classes with excluded minors.