Paper Info
Title
Parameterized Complexity for Uniform Operators on Multidimensional Analytic Functions and ODE Solving.
Abstract
Real complexity theory is a resource-bounded refinement of computable analysis and provides a realistic notion of running time of computations over real numbers, sequences, and functions by relying on Turing machines to handle approximations of arbitrary but guaranteed absolute error. Classical results in real complexity show that important numerical operators can map polynomial time computable functions to functions that are hard for some higher complexity class like NP or #P. Restricted to analytic functions, however, those operators map polynomial time computable functions again to polynomial time computable functions. Recent work by Kawamura, Muller, Rosnick and Ziegler discusses how to extend this to uniform algorithms on one-dimensional analytic functions over simple compact domains using second-order and parameterized complexity. In this paper, we extend some of their results to the case of multidimensional analytic functions. We further use this to show that the operator mapping an analytic ordinary differential equations to its solution is computable in parameterized polynomial time. Finally, we discuss how the theory can be used as a basis for verified exact numerical computation with analytic functions and provide a prototypical implementation in the iRRAM C++ framework for exact real arithmetic.
Year
DOI
Venue
2018
10.1007/978-3-662-57669-4_13
Lecture Notes in Computer Science
Field
DocType
Volume
Complexity class,Applied mathematics,Discrete mathematics,Parameterized complexity,Computer science,Analytic function,Turing machine,Operator (computer programming),Time complexity,Computable function,Computable analysis
Conference
10944
ISSN
Citations 
PageRank 
0302-9743
0
0.34
References 
Authors
7
3
Name
Order
Citations
PageRank
Akitoshi Kawamura110215.84
Florian Steinberg201.69
Holger Thies301.35