Geometrische Komplexitätstheorie

• Antragsteller: Dr. Christian Ikenmeyer
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2018 bis 2023
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 408113219

Das wohl bekannteste Problem im Schnittpunkt zwischen theoretischer Informatik und Mathematik ist das berühmte P-NP-Problem. Um einer Lösung näher zu kommen führte Valiant 1979 eine Algebraisierung von P-NP ein, welche heute als Determinante vs Permanente (det vs per) bekannt ist. Mulmuley und Sohoni interpretierten det vs per 2001 geometrisch und gründeten die geometrische Komplexitätstheorie (GCT), einen Ansatz, um fundamentale untere Komplexitätsschranken mittels alg. Geometrie, Darstellungstheorie und alg. Kombinatorik zu zeigen. Dieser Antrag hat 2 Ziele: (1) die Beantwortung fundamentaler Fragen in der GCT und (2) den Beweis expliziter unterer Komplexitätsschranken mittels GCT. In Ziel (1) wollen wir die Auswirkungen der algebraischen natürliche-Beweise-Barriere auf GCT verstehen, wir wollen die GCT Vermutungen mit klassischen Vermutungen aus der algebraischen Komplexitätstheorie in Zusammenhang stellen, und wir wollen die fundamentalen Unterschiede zwischen Occurrence Obstructions und Multiplicity Obstructions verstehen, welches zwei Methoden der GCT sind, um untere Komplexitätsschranken zu zeigen. In Ziel (2) führen wir neue algebraische Komplexitätsmaße ein, welche polynomiell äquivalent zu klassischen Komplexitätsmaßen sind, welche aber zahmere Geometrie und Darstellungstheorie besitzen. Insbesondere möchten wir die homogene iterierte Matrixmultiplikationskomplexität, die homogene Spur-der-Potenz-Komplexität, die Grenz-Breite-2-ABP-Komplexität und die Grenzkontinuantenkomplexität studieren.

• DFG-Verfahren: Sachbeihilfen
• Internationaler Bezug: Großbritannien