Carsten Rosnick Parametrisierte uniforme Berechnungskomplexitat in Geometrie und Numerik

Annotation

Carsten Rosnick legt seiner Arbeit die Frage nach der algorithmischen Komplexitat der approximativen Berechnung von Operatoren aus Geometrie, Topologie und Analysis zugrunde. Er betrachtet Operatoren wie Mengendurchschnitt, Projektion, Maximierung, Integration und Funktionsinversion. Der Begriff der Komplexitat ist hierbei im rigorosen Sinne von garantierten Laufzeitschranken und asymptotischen Optimalitatsbeweisen zu verstehen. Dazu fuhrt der Autor Kodierungen fur Mengen und Funktionen ein und untersucht sie hinsichtlich ihrer (Polynomialzeit-)Aquivalenz, um schlielich in der Bestimmung parametrisierter Komplexitatsschranken fur obige Operatoren Verwendung zu finden.