"Complexity Theory of (Functions on) Compact Metric Spaces"

(joint work with Akitoshi Kawamura and Florian Steinberg)

We promote the theory of computational complexity on metric spaces: as natural common generalization of 
(i) the classical discrete setting of integers, binary strings, graphs etc. as well as of (ii) the 
bit-complexity theory on real numbers and functions according to Friedman, Ko (1982ff), Cook, Braverman 
et al.; as (iii) resource-bounded refinement of the theories of computability on, and representations of, 
continuous universes by Pour-El&Richards (1989) and Weihrauch (1993ff); and as (iv) computational 
perspective on quantitative concepts from classical Analysis: Our main results relate (i.e. upper and 
lower bound) Kolmogorov's entropy of a compact metric space $X$ polynomially to the uniform relativized 
complexity of approximating various families of continuous functions on $X$. The upper bounds are 
attained by carefully crafted oracles and bit-cost analyses of algorithms perusing them. They all employ 
the same representation (i.e. encoding, as infinite binary sequences, of the elements) of such spaces, 
which thus may be of own interest. The lower bounds adapt adversary arguments from unit-cost 
Information-Based Complexity to the bit model. They extend to, and indicate perhaps surprising 
limitations even of, encodings via binary string functions (rather than sequences) as introduced by 
Kawamura&Cook (SToC'2010,\S3.4). These insights offer some guidance towards suitable notions of 
complexity for higher types.