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

• Antragsteller: Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2007 bis 2008
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 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-Verfahren: Sachbeihilfen