Rekursive Analysis ist die von Alan Turing initiierte Berechenbarkeitstheorie über reellen Zahlen und Funktionen im Sinne rationaler Approximationen bis auf beliebig vorgebbaren Absolutfehler 1/2^N, sowie allgemeiner über einem Universum kontinuierlicher Mächtigkeit bzgl. einer festen Kodierung seiner Elemente als unendliche Binärfolgen mittels Typ-2 Maschinen (vgl. Weihrauch 2000). Diese Sichtweise komplementiert die Ingenieursnumerik, in der typischerweise die Eingabedimension (z.B. Matrixgröße) als 'groß', die Rechengenauigkeit hingegen als fix (z.B. double) angenommen wird. Sie modelliert Arithmetik adaptiver Genauigkeit mit Bibliotheken wie MPFR, GMP oder iRRAM. Dass hierbei einwertige Tests unstetig und damit unberechenbar ('Hauptsatz') sind, macht die Behandlung mehrwertiger (d.h. intensionaler) Funktionen unvermeidbar.Eine komplexitätstheoretische Verfeinerung reiner Berechenbarkeit entwickelten seit den 80er und 90er Jahren u.a. H.Friedman, K.-I.Ko und N.T.Müller für (einwertige) reelle Funktionen sowie für Operatoren wie Maximum, Integral und die Lösung gewöhnlicher Differentialgleichungen: nichtuniform, d.h. bspw. für eine polynomialzeitberechenbare analytische Funktion ist ihr Integral zwar als seinerseits wieder polynomialzeitberechenbar bekannt, nicht jedoch wie (und mit welchen diskreten Zusatzinformationen) man aus einem polynomiellen Algorithmus für ersteres einen ebensolchen für letzteres bekommt --- und wie beide Laufzeiten quantitativ von einander abhängen. Tatsächlich hatten einen zufriedenstellenden Begriff für uniforme effiziente Berechenbarkeit von Operatoren Akitoshi Kawamura und Stephen A. Cook (2010) gefunden in Termen von sogenannten Polynomen zweiter Ordnung, vgl. Mehlhorn (1976) und Kapron&Cook (1996).Wir stratifizieren diese strukturelle zu einer quantitativen Komplexitätstheorie und erweitern sie auf mehrwertige Funktionen und Operatoren. Genauer analysieren wir bekannte und entwickeln neue Algorithmen im Hinblick auf den Exponenten ihrer (in der Ausgabegenauigkeit N) polynomiellen Laufzeit und seiner Abhängigkeit von Parametern des betrachteten (Funktionen-)Raums. Dies wird eine realistischere Einschätzung ihrer praktischen Effizienz ermöglichen und die Verbindungen zur Praxis der Intervallarithmetik / validierten Numerik stärken. Komplementäre untere Komplexitätsschranken deduzieren wir aus quantitativen Analysen des Moduls der (mehrwertigen) Stetigkeit der betrachteten Funktionen und Operatoren --- und seiner Verallgemeinerung auf den mehrwertigen Fall (Pauly&Ziegler 2011). Um diesbezügliche Abschätzungen zu erhalten, adaptieren wir Adversary-Methoden aus der Informations-basierten Komplexität (IBC, ursprünglich zum Blum-Shub-Smale Modell korrespondierend) an die Gegebenheiten der Rekursiven Analysis, wo eine Funktionsauswertung approximative Aus- wie auch Eingaben involviert und damit nicht-lokale Informationen liefert.

DFG-Verfahren Sachbeihilfen

Internationaler Bezug Japan

Beteiligte Personen Dr. Akitoshi Kawamura, Ph.D.; Professor Dr. Norbert Müller

Ehemaliger Antragsteller Professor Dr. Martin Ziegler, bis 8/2015