Gibt es eine Logik für PTIME?

Die deskriptive Komplexitätstheorie stellt eine Beziehung zwischen der
Berechnungskomplexität von algorithmischen Problemen und ihrer sprachlichen
Komplexität her; stark vereinfacht sind algorithmische Probleme, die schwer zu
beschreiben sind, auch schwer zu lösen und umgekehrt. Der Wert solcher
sprachlicher oder logischer Charakterisierungen von Komplexitätsklassen
besteht darin, dass sie einen Zugang zur Komplexität liefern, der unabhängig
von Maschinenmodellen sowie der konkreten Repräsentation der Eingabedaten ist.

Während für viele Komplexitätsklassen logische Charakterisierungen bekannt
sind, kennen wir ausgerechnet für die wichtige Klasse PTIME, dem gängigen
mathematischen Modell der Klasse der "effizient lösbaren" Probleme, keine
solche Charakterisierung. Die Frage nach einer logischen Charakterisierung
von PTIME wurde zuerst 1982 von Chandra und Harel im Rahmen der
Datenbanktheorie gestellt und gilt seitdem als eine zentrale offene Frage der
Datenbanktheorie und der deskriptiven Komplexitätstheorie.

In diesem Projekt sollen verschiedene Aspekte der Frage untersucht
werden. Insbesondere soll eine logische Charakterisierung für eine
große Klasse von "kombinatorisch einfachen" Problemen in PTIME
gegeben werden.