Sommerakademie der Studienstiftung
St. Johann, 30.8.-12.9.1998
Arbeitsgruppe 4: Quo vadis, Komplexitätstheorie?
Standen in der klassischen Rekursionstheorie vor allem Fragen der
prinzipiellen Berechenbarkeit von Problemen im Mittelpunkt des Interesses,
so beschäftigt sich die heutige Komplexitätstheorie vor allem mit der Frage
der Berechenbarkeit innerhalb vorgegebener Ressourcen
und im Rahmen bestimmter Rechnermodelle.
Hierbei hat es sich gezeigt, daß verschiedene Arten von Ressourcen (wie z.B.
Zeit, Platz, Nichtdeterminismus, Parallelität) oft in sehr
grundsätzlichem, aber auch komplexem Zusammenhang stehen und die Hinzunahme
solcher Ressourcen (z.B. Randomisierung) drastische Auswirkungen auf die
Komplexität von Problemen haben kann.
In unserer Arbeitsgruppe wollen wir diesen Paradigmen an Hand von
ausgewählten Beispielen nachgehen und dabei insbesondere auch Querbeziehungen
zu benachbarten Gebieten (Kryptographie, Optimierung, Geometrie) untersuchen.
