Quantitative Uniform Complexity Theory of Multivalued Real Functions and Operators in Analysis
Mathematics
Final Report Abstract
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.
Publications
- “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
(See online at 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
(See online at 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
(See online at 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
(See online at https://doi.org/10.1017/S096012951600013X)
