Strukturelle Komplexitätstheorie für Big Data - Von Klassifikationstheoremen bis Algorithm Engineering

• Antragsteller: Professor Dr.-Ing. Marvin Künnemann
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung seit 2021
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 462679611

Angesichts stetig wachsender Datenmengen besteht eine bedeutende Aufgabe der modernen Komplexitätstheorie darin, neue Methoden zu entwickeln, um beweisen zu können, wann ein algorithmisches Problem auf riesigen Datenmengen schwer zu lösen ist. Die Theorie der feinkörnigen Reduktionen in P empfiehlt sich hierbei als viel versprechende Kandidatin, nicht zuletzt dank der Beiträge des Antragsstellers. Dies führt zu der Frage: Vermag es diese Theorie, eine Entsprechung der NP-Schwere für die Big-Data-Welt darzustellen? Um eine wirkliche Entsprechung zu liefern, besteht die wahrscheinlich größte theoretische Herausforderung darin, den aktuell sehr problembezogenen Forschungsstand zu einer umfassenderen Theorie auszubilden. Dementsprechend ist das Hauptziel dieses Antrages, Klassifikationstheoreme für Klassen von Polynomialzeitproblemen zu entwickeln, ähnlich zu Schaefers Theorem und dem sich anschließenden Dichotomie-Theorem, das eindrucksvoll die Erklärungskraft der NP-Schwere auf Constraint-Satisfaction-Problemen verdeutlicht. Für diese Aufgabe liegt der besondere Fokus auf der Klasse der Modellprüfungsprobleme für prädikatenlogische Ausdrücke erster Stufe, denen eine wichtige Bedeutung für die Logik, theoretische Informatik und relationalen Datenbanken innewohnt. Von einer systematischen Klassifikation -- selbst dann, wenn sie nur teilweise erfolgreich ist -- kann erwartet werden, dass sie die Komplexitätslandschaft von Polynomialzeitproblemen deutlich besser strukturieren kann als es isolierte Ergebnisse könnten, womit wichtige technische Herausforderungen herausgestellt werden und weiterer Fortschritt ermöglicht werden kann. Angesichts der Bedeutung prädikatenlogischer Aussagen erster Stufe verfolgt dieser Antrag auch eine pragmatische Herangehensweise an die motivierende Frage und sieht vor, den entstehenden theoretischen Einsichten praktische Untersuchungen gegenüberzustellen: Wie können wir hervorgehende feinkörnige Reduktionen in P für das Algorithm Engineering auf großen Datenmengen nutzen, insbesondere für Information Retrieval, Geographische Informationssysteme und Graphentheorie? Eine umfassende Studie könnte neue Techniken für Aspekte wie die Erstellung von Benchmarks, die Optimierung relationaler Datenbankanfragen, und den allgemeinen Algorithmenentwurf auf großen Datenmengen enthüllen.

• DFG-Verfahren: Emmy Noether-Nachwuchsgruppen