TY - GEN
T1 - Towards computational complexity theory on advanced function spaces in analysis
AU - Kawamura, Akitoshi
AU - Steinberg, Florian
AU - Ziegler, Martin
N1 - Funding Information:
Supported in part by JSPS Kakenhi projects 24106002 and 26700001, by EU FP7 IRSES project 294962, by DFG Zi 1009/4-1 and by IRTG 1529. We thank Daniel Graça and Elvira Mayordomo for inviting this extended abstract as opportunity to report on our progress since its CCA 2015 short version.
Publisher Copyright:
© Springer International Publishing Switzerland 2016.
PY - 2016
Y1 - 2016
N2 - Pour-El and Richards [PER89], Weihrauch [Weih00], and others have extended Recursive Analysis from real numbers and continuous functions to rather general topological spaces. This has enabled and spurred a series of rigorous investigations on the computability of partial differential equations in appropriate advanced spaces of functions. In order to quantitatively refine such qualitative results with respect to computational efficiency we devise, explore, and compare natural encodings (representations) of compact metric spaces: both as infinite binary sequences (TTE) and more generally as families of Boolean functions via oracle access as introduced by Kawamura and Cook ([KaCo10], Sect. 3.4). Our guide is relativization: Permitting arbitrary oracles on continuous universes reduces computability to topology and computational complexity to metric entropy in the sense of Kolmogorov. This yields a criterion and generic construction of optimal representations in particular of (subsets of) Lp and Sobolev spaces that solutions of partial differential equations naturally live in.
AB - Pour-El and Richards [PER89], Weihrauch [Weih00], and others have extended Recursive Analysis from real numbers and continuous functions to rather general topological spaces. This has enabled and spurred a series of rigorous investigations on the computability of partial differential equations in appropriate advanced spaces of functions. In order to quantitatively refine such qualitative results with respect to computational efficiency we devise, explore, and compare natural encodings (representations) of compact metric spaces: both as infinite binary sequences (TTE) and more generally as families of Boolean functions via oracle access as introduced by Kawamura and Cook ([KaCo10], Sect. 3.4). Our guide is relativization: Permitting arbitrary oracles on continuous universes reduces computability to topology and computational complexity to metric entropy in the sense of Kolmogorov. This yields a criterion and generic construction of optimal representations in particular of (subsets of) Lp and Sobolev spaces that solutions of partial differential equations naturally live in.
UR - http://www.scopus.com/inward/record.url?scp=84976609574&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84976609574&partnerID=8YFLogxK
U2 - 10.1007/978-3-319-40189-8_15
DO - 10.1007/978-3-319-40189-8_15
M3 - Conference contribution
AN - SCOPUS:84976609574
SN - 9783319401881
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 142
EP - 152
BT - Pursuit of the Universal - 12th Conference on Computability in Europe, CiE 2016, Proceedings
A2 - Jonoska, Nataša
A2 - Bienvenu, Laurent
A2 - Beckmann, Arnold
PB - Springer Verlag
T2 - 12th Conference on Computability in Europe, CiE 2016
Y2 - 27 June 2016 through 1 July 2016
ER -