Schaltkreiskomplexität, Parametrische Komplexität und logische Definierbarkeit
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.
Mittelgeber
DFG: Sachbeihilfe
Laufzeit
Projektstart: 10/2010
Projektende: 11/2012
