Quantitative uniforme Komplexitätstheorie mehrwertiger reeller Funktionen und Operatoren in Analysis
Mathematik
Zusammenfassung der Projektergebnisse
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.
Projektbezogene Publikationen (Auswahl)
- “Relative Computability and Uniform Continuity of Relations”, S.1–39, Journal of Logic and Analysis vol.5:7 (2013)
A. Pauly, M. Ziegler
- Parametrisierte uniforme Berechnungskomplexität in Geometrie und Numerik, Springer (2015), ISBN 3658096586
C. Rösnick
- “Base-Complexity Classifications of QCB0-Spaces”, S.156–166, Proc. 11th Conf. on Computability in Europe (CiE’2015), Springer LNCS vol.9136
M. de Brecht, M. Schröder, V. Selivanov
(Siehe online unter https://dx.doi.org/10.3233/COM-150044) - “Computational Benefit of Smoothness: Parameterized Bit-Complexity of Numerical Operators on Analytic Functions and Gevrey’s Hierarchy”, S.689–714, Journal of Complexity vol.31:5 (2015)
A. Kawamura, N. Müller, C. Rösnick, M. Ziegler
(Siehe online unter https://doi.org/10.1016/j.jco.2015.05.001) - “Average-Case Bit-Complexity Theory of Real Functions”, S.505–519, Proc. 6th Int. Conf. Mathematical Aspects of Computer and Information Sciences (MACIS’2015), Springer LNCS vol.9582 (2016)
M. Schröder, F. Steinberg, M. Ziegler
(Siehe online unter https://doi.org/10.1007/978-3-319-32859-1_43) - “On the Computational Complexity of the Dirichlet Problem for Poisson’s Equation”, Mathematical Structures in Computer Science
Volume 27, Special Issue 8 (Continuity, Computability, Constructivity: From Logic to Algorithms 2013), December 2017, pp. 1437-1465
A. Kawamura, F. Steinberg, M. Ziegler
(Siehe online unter https://doi.org/10.1017/S096012951600013X)
