Deskriptive Komplexitätstheorie kleiner Komplexitätsklassen

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

• Final Report Year: 2013

Final Report Abstract

In der deskriptiven Komplexitätstheorie versucht man, logische Charakterisierungen von Komplexitätsklassen zu geben, Komplexität also mit sprachlichen Mitteln zu erfassen. Seit langem bekannt sind logische Charakterisierungen der Komplexitätsklassen NP und co-NP sowie der meisten natürlichen Komplexitätsklassen, die eine dieser beiden Klassen enthalten. Für die Klasse PTIME und darin enthaltene Klassen wie LOGSPACE sind hingegen keine (oder nur eingeschränkte) logische Charakterisierungen bekannt. Es gilt als das wichtigste offene Problem der deskriptiven Komplexitätstheorie, eine solche Charakterisierung zu finden. Thema dieses Projekts waren verschiedene Fragen im Umkreis dieses offenen Problems. Die wichtigsten Ergebnisse sind die folgenden: 1) Charakterisierungen von PTIME auf eingeschränkten Strukturklassen, darunter Intervallgraphen und alle Klassen von Graphen mit verbotenen topologischen Subgraphen. Das sind die umfassendsten bekannten logischen Charakterisierungen von PTIME. Die Resultate haben auch einen Bezug zum Graphenisomorphieproblem. 2) Entwicklung einer neuartigen Logik, die die Logik der ersten Stufe um einen eingeschränkten Rekursionsoperator erweitert. Diese Logik charakterisiert LOGSPACE auf verschiedenen Strukturklassen, darunter Bäume und Intervallgraphen. Damit sind uns die ersten Charakterisierungen der Klasse LOGSPACE auf Strukturen ohne lineare Ordnung gelungen. 3) Erste nichttriviale Nichtausdrückbarkeitsergebnisse zur Fixpunktlogik mit Rangoperatoren, die als eine der Kandidatenlogiken für eine logische Charakterisierung von PTIME gilt. 4) Ein neues Konzept von probabilistischen Komplexitätsklassen, das logische Charakterisierungen von probabilistischen Komplexitätsklassen wie BPP ermöglicht. Die Logiken ermöglichen auch eine logische Analyse von Derandomisierungsfragen, die in der Komplexitätstheorie eine große Rolle spielen.

Publications

• Capturing polynomial time on interval graphs. Logic in Computer Science (LICS), 2010 25th Annual IEEE Symposium on 11-14 July 2010, pp. 199-208.
  B. Laubner
  
• Structure theorem and isomorphism test for graphs with excluded topological subgraphs. In Proceedings of the 44th ACM Symposium on Theory of Computing, 2012, pp. 173-192,
  M. Grohe, D. Marx
  
• L-recursion and a new logic for logarithmic space. Logical Methods in Computer Science, Vol. 9. 2013, Issue 1, Paper 11.
  M. Grohe, B. Gruien, A. Hernich, B. Laubner