Logik, Struktur und das Graphenisomorphieproblem

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

Eine wichtige Erkenntnis der Komplexitätstheorie, die sich im Lauf der letzten vierzig Jahre verfestigt hat, besteht darin, dass die allermeisten natürlichen und praktisch relevanten kombinatorischen Such- und Optimierungsprobleme entweder in der Komplexitätsklasse P liegen oder aber vollständig für die Klasse NP sind. Stark vereinfacht bedeutet diese Dichotomie, dass die Probleme entweder effizient algorithmisch lösbar oder nur sehr schwer zu lösen sind, aber eben nicht „mittelschwer“. Eines der ganz wenigen natürlichen Probleme dieser Art, für das man bislang weder die Zugehörigkeit zu P noch die NP-Vollständigkeit nachweisen konnte, das also eine Ausnahme von der beobachteten Dichotomie bilden könnte, ist das Graphenisomorphieproblem, welches im Mittelpunkt dieses Projekts steht.Die Frage nach der Komplexität des Isomorphieproblems ist ein prominentes und seit über vierzig Jahren offenes Problem der theoretischen Informatik. Seit den frühen 1980er Jahren stehen bei der theoretischen Untersuchung des Isomorphieproblems gruppentheoretische Methoden im Vordergrund. Ausgangspunkt für diesen Antrag hingegen sind Techniken der modernen Graphenstrukturtheorie sowie Techniken aus der Logik, genauer der endlichen Modelltheorie, von denen bekannt ist, dass sie in engem Zusammenhang mit kombinatorischen Ansätzen zur Lösung des Isomorphieproblems stehen.

• DFG Programme: Reinhart Koselleck Projects