Reelle Komplexitätstheorie ist eine Weiterentwicklung der Rekursiven Analysis: Initiiert durch Alan Turing untersucht letztere Probleme aus der Analysis (transzendente Zahlen, Folgen/Grenzwerte, Funktionen, Operatoren, Euklidische Mengen) im Hinblick auf ihre Berechenbarkeit im Sinn algorithmischer Approximation bis auf Absolutfehler 2-n; und erstere im Hinblick auf effiziente Berechenbarkeit zur Anwendung beispielsweise in computerunterstützten Beweisen. Das vorliegende Projekt hat die Reelle Komplexitätstheorie signifikant weiterentwickelt und verfeinert - und ist so dem langfristigen Ziel erheblich näher gekommen, die Konzepte und Methoden der Theoretischen Informatik vom Diskreten auf numerische (d.h. kontinuierliche) Probleme zu übertragen: • Nicht-uniforme Polynomialzeitresultate und Algorithmen für analytische Funktionen wurden uniform parametrisiert verschärft, • der Nutzen von Glattheitsvoraussetzungen der Daten zur Effizienzsteigerung im Bitkostenmaß rigoros analysiert, • der komplexitätstheoretische Phasenübergang von unendlich oft differenzierbaren zu analytischen Funktionen aufgelöst • und mit den Stufen der klassischen Gevrey Hierarchie verknüpft. • Wir haben die gängige worst-case Komplexitätstheorie zum realistischeren average-case im Reellen weiterentwickelt, • klassische diskrete Komplexitätsklassen numerisch charakterisiert • und mit partiellen Differentialgleichungen ein aktuelles Thema der Numerik komplexitätstheoretisch erschlossen • sowie die Mächtigkeit bzw. der komplexitätstheoretische Einfluß von Mehrwertigkeit/Nichtextensionalität bzw. enrichment/advice ausgelotet: Aspekte, welche die engen Beziehungen zwischen Analysis, Numerik, Theoretischer Informatik und Logik illustrieren. Interessanterweise stellte sich beispielsweise heraus, dass die Lösung der partiellen aber linearen Laplace und Poisson-Gleichung komplexitätstheoretisch leichter ist als jene gewöhnlicher Differentialgleichungen mit Lipschitz-stetiger rechter Seite. Überraschend war auch die Erkenntnis, dass die Kodierung kompakter Euklidischer Mengen durch ihre Distanzfunktionen in p-Norm paarweise nichtüquivalent sind hinsichtlich Polynomialzeitberechenbarkeit. Die Resultate wurden durch die Projektmitarbeiter gemeinsam mit nationalen und internationalen Kooperationspartnern (wie bspw. Akitoshi Kawamura von der Universität Tokio) erarbeitet.