Schaltkreiskomplexität, Parametrische Komplexität und logische Definierbarkeit

• Antragsteller: Professor Dr. Martin Grohe
• Fachliche Zuordnung: Theoretische Informatik
• Förderung: Förderung von 2010 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 186219630

Fragen nach unteren Schranken für die Komplexität algorithmischer Probleme gehören zu den schwierigsten der theoretischen Informatik, beispielsweise ist das berühmte P vs. NP Problem von diesem Typ. Zumeist sind diese Fragen trotz großer Anstrengungen noch offen. Die bislang erzielten Ergebnisse sind eher bescheiden, aufgrund der fundamentalen Bedeutung des Begriffs der Komplexität für die Informatik aber dennoch wichtig. Erzielt werden konnten die meisten dieser Ergebnisse durch die kombinatorische Analyse von Schaltkreisen. Aus der deskriptiven Komplexitätstheorie ist ein enger Zusammenhang zwischen Logik und Komplexität bekannt; Fragen nach unteren Schranken übersetzen sich damit in Fragen nach der Ausdrucksstärke von Logiken. Der Zusammenhang zwischen Logik und Schaltkreiskomplexität soll auch im Mittelpunkt dieses Projekts stehen. Ein wesentlicher neuer Aspekt ist dabei die Einbeziehung von Sichtweisen und Resultaten der parametrischen Komplexitätstheorie, einem relativ neuen Zweig der Komplexitätstheorie, der eine verfeinerte Analyse von Problemen anhand mehrerer Parameter erlaubt. Konkret wollen wir versuchen, gewisse Hierarchien von Komplexitätsklassen in der Schaltkreiskomplexität zu etablieren sowie konkrete untere Schranken für parametrische Probleme anzugeben und damit eine parametrische Schaltkreiskomplexität einzuführen. Auf der logischen Seite wollen wir Ausdrucksstärke und Formellängen von Logiken mit endlich vielen Variablen untersuchen.

• DFG-Verfahren: Sachbeihilfen