Deskriptive Komplexitätstheorie kleiner Komplexitätsklassen

<p>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. Logische Charakterisierungen von Komplexitätsklassen sind auch in der
Datenbanktheorie von Relevanz, tatsächlich haben zentrale Fragen der deskriptiven Komplexitätstheorie dort ihren Ursprung.</p>

<p>Während für die Komplexitätsklasse NP und die meisten natürlichen
Erweiterungen von NP logische Charakterisierungen bekannt sind, kennen wir für
Teilklassen von NP, insbesondere für die wichtige Klasse PTIME, dem gängigen
mathematischen Modell der Klasse der "effizient lösbaren" Probleme, keine
solchen Charakterisierungen. Die Frage nach einer logischen Charakterisierung
von PTIME geht auf eine Arbeit über Datenbankanfragesprachen von Chandra und Harel aus dem Jahre 1982 zurück.</p>

<p>In diesem Projekt sollen verschiedene Aspekte der deskriptiven
Komplexitätstheorie untersucht werden. Wir wollen uns im Wesentlichen auf die
Klasse PTIME und Teilklassen (die "kleinen Komplexitätsklassen" im Titel)
konzentrieren, für die das technische Problem der Repräsentationsinvarianz von
Algorithmen eine zentrale Rolle spielt.</p>