Gibt es eine Logik für PTIME? (Forschungssemester)

• Applicant: Professor Dr. Martin Grohe
• Subject Area: Theoretical Computer Science
• Term: from 2007 to 2008
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 61560798

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 1 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.

• DFG Programme: Research Grants