Logik, Struktur und das Graphenisomorphieproblem

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