Descriptive Complexity and Semantically Defined Fragments of Ptime. Martin Otto's abstract for FMT and ST meeting, 7 Jan 1999

Descriptive Complexity and Semantically Defined Fragments of Ptime. Abstract

Martin Otto (RWTH-Aachen)

The "Logic for Ptime" issue, or the question whether recursive syntax can be given for the class of precisely those properties of finite structures which are of polynomial time complexity, is one of the long-standing research incentives in finite model theory. While there may be less hope to settle the overall question in the positive, a few interesting fragments of Ptime have emerged, defined in terms of stronger invariance conditions than the obvious isomorphism invariance, for which the issue could be settled positively. This is achieved in a combination of techniques based on logical games, concise invariants derived from these, and combinatorial canonization procedures. In this talk I will focus on the general ideas and techniques, their successes and limitations, and discuss one particularly neat case in point, namely a capturing result for the "modal" fragment as defined by the condition of bisimulation invariance.