Quantitative Uniform Complexity Theory of Multivalued Real Functions and Operators in Analysis

• Applicant: Professor Dr. Thomas Streicher, since 8/2015
• Subject Area: Theoretical Computer Science ; Mathematics
• Term: from 2013 to 2016
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 229100744

• Final Report Year: 2016

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
  
• “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
  
• “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
  
• “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