TU Darmstadt / ULB / TUprints

Computational Complexity Theory for Advanced Function Spaces in Analysis

Steinberg, Florian (2017)
Computational Complexity Theory for Advanced Function Spaces in Analysis.
Technische Universität Darmstadt
Ph.D. Thesis, Primary publication

[img]
Preview
Text
diss.pdf
Copyright Information: CC BY 4.0 International - Creative Commons, Attribution.

Download (1MB) | Preview
Item Type: Ph.D. Thesis
Type of entry: Primary publication
Title: Computational Complexity Theory for Advanced Function Spaces in Analysis
Language: English
Referees: Ziegler, Prof. Dr. Martin ; Kohlenbach, Prof. Dr. Ulrich ; Kawamura, Prof. Dr. Akitoshi
Date: 1 February 2017
Place of Publication: Darmstadt
Date of oral examination: 2 November 2016
Abstract:

This PhD thesis presents progress in the search for a mathematical rigorous framework for efficient numerics of partial differential equations based on a realistic machine model. While the computability theory of continuous structures is well developed and still an active field of research, in most settings it remains unclear what computations should be considered feasible. This problem is tackled within the framework of second-order representations. The name as well as the notion of polynomial-time computability of the framework is inherited from the complexity theory of functionals on the Baire space, also called second-order complexity theory. As model of computation we use oracle Turing machines. Second-order representations offer a great deal of freedom in developing models of computation and a supply of well investigated structures. In particular, there exists an established second-order representation of the set of continuous functions on the unit interval. This representation has been classified as the weakest representation such that evaluation is possible in polynomial time. As a first step we specify the weakest representation of the integrable functions such that integration is polynomial-time computable. This representation turns out to be discontinuous and therefore not suitable. We go on to explore the general restrictions of bounded-time computations on metric spaces within the framework of second-order representations. The notion of metric entropy, originally introduced by Kolmogorov, is used to classify those compact metric spaces that allow for a short representation such that the metric is computable efficiently. To be able to apply the results to spaces of integrable functions we investigate quantitative versions of classification results of their compact subsets called the Arzelà-Ascoli Theorem and the Fréchet-Kolmogorov Theorem. We use the above to propose a family of representations for Lp-spaces. These are shown to be computably equivalent to the standard representations of the same spaces as metric spaces. Furthermore, we prove that the norm can be computed in exponential time. This is also the case for the supremum norm on the continuous functions on the unit interval. A similar family of representations is presented for Sobolev spaces. These representations are investigated in some detail. Several operators on Sobolev spaces are proven to be polynomial-time computable with respect to these representations. For technical reasons only the one-dimensional case is discussed. Finally, we present a result that classifies the computational complexity of the solution operator of the Dirichlet Problem for Poisson’s Equation on the unit disk as that of integrating a continuous function. As a tool for the comparison, polynomial-time Weihrauch reductions are used.

Alternative Abstract:
Alternative AbstractLanguage

Motivation für diese Doktorarbeit ist das Vorantreiben der Suche nach einem auf ei- nem realistisches Maschinenmodell basierenden, mathematisch rigorosen Rahmen für Effizienzüberlegungen über die Numerik partieller Differenzialgleichungen. Während die Berechenbarkeitstheorie für kontinuierliche Strukturen auf die meisten Situationen an- wendbar ist und beständig weiter entwickelt wird, ist es selbst in simplen Fällen oft noch unklar, welche Algorithmen als effizient zu gelten haben. In dieser Arbeit wird das Problem im Rahmen der Darstellungen zweiter Ordnung angegangen. Diese beziehen sowohl ihren Namen, als auch ihren Begriff von Polyno- mialzeitberechenbarkeit aus der Komplexitätstheorie der Funktionale auf dem Baire Raum, auch Komplexitätstheorie zweiter Ordnung genannt. Als Maschinenmodell die- nen Orakel-Turingmaschinen. Die Darstellungen zweiter Ordnung bieten viel Freiraum in der Gestaltung von Rechenmodellen und auch einen Grundstock an Konstruktuionen und behandelten Problemen. Insbesondere existiert eine etablierte Darstellung für das Rechnen mit stetigen Funktionen auf dem Einheitsintervall. Diese ist als die schwächste charakterisiert, die eine Auswertung in Polynomialzeit möglich macht. Als ein erster Schritt wird die schwächste Darstellung zweiter Ordnung für die in- tegrierbaren Funktionen angegeben, die es ermöglicht in Polynomialzeit Integrale aus- zuwerten. Unglücklicherweise erweist sich diese als unstetig und damit ungeeignet. Auf der Suche nach einer geeigneteren Darstellung werden die generellen Beschränkungen des Rechnens mit Darstellungen zweiter Ordnung auf metrischen Räumen untersucht. Dabei spielt die von Kolmogorov eingeführte metrische Entropie eines kompakten metrischen Raumes eine tragende Rolle. Es stellt sich heraus, dass es einen direkten Zusammenhang zwischen dieser und der Existenz ‘kurzer’ Darstellungen gibt, bezüglich derer sich die Me- trik ‘schnell’ berechnen lässt. Um diese Resultate auf Räume integrierbarer Funktionen anwendbar zu machen, werden quantitative Versionen der Klassifikationsresultate kom- pakter Teilmengen, bekannt als die Sätze von Arzelà-Ascoli und Fr´ echet-Kolmogorov, untersucht. Auf die gewonnen Erkenntnisse gestützt wird eine Familie von Darstellungen für L p - Räume konstruiert. Es wird beweisen, dass diese berechenbar äquivalent zu den Darstel- lungen selbiger Räume als metrische Räume sind und gezeigt, dass sie die L p -Norm in Exponentialzeit berechnenbar machen. Dies ist auch die Komplexität der Supremums Norm auf den stetigen Funktionen. Eine ähnliche Konstruktion führt zu Darstellungen von Sobolev-Räumen. Die Berechenbarkeit unterschiedlichster Operationen in Polyno- mialzeit wird gezeigt, aus technischen Gründen nur für den eindimensionalen Fall. Abschließend wird ein Resultat präsentiert, das die Schwierigkeit des Berechnens des Lösungsoperators zum Dirichlet-Problem für Poisson’s Gleichung auf der Einheitskugel gleichsetzt mit der Schwierigkeit eine stetigen Funktion zu integrieren. Zum Verglei- chen von Schwierigkeiten von Aufgaben werden Polynomialzeit-Weihrauch-Reduktionen verwendet.

German
URN: urn:nbn:de:tuda-tuprints-60964
Classification DDC: 500 Science and mathematics > 510 Mathematics
Divisions: 04 Department of Mathematics > Logic
Date Deposited: 02 May 2017 14:38
Last Modified: 09 Jul 2020 01:35
URI: https://tuprints.ulb.tu-darmstadt.de/id/eprint/6096
PPN: 402710959
Export:
Actions (login required)
View Item View Item